凛音中文字幕,93人妻免费

遞歸回溯這類(lèi)題目的代碼往往會(huì)包含一個(gè)遞歸函數(shù)和遞歸函數(shù)內(nèi)部的一個(gè)循環(huán)語(yǔ)句。

比如N皇后問(wèn)題，它每次遞歸時(shí)，就進(jìn)入到下一行做一些邏輯處理。而在每一行時(shí)，都會(huì)循環(huán)遍歷每一列，判斷本行該列的元素是否滿(mǎn)足條件。又比如電話(huà)號(hào)碼的字母組合問(wèn)題，每遞歸一次就進(jìn)入到下一個(gè)數(shù)字，然后遍歷該數(shù)字對(duì)應(yīng)的字母列表。其他問(wèn)題也類(lèi)似，但會(huì)有一定的變形。

既然都有遞歸和循環(huán)結(jié)構(gòu)，并且遞歸和循環(huán)都沿著這兩個(gè)結(jié)構(gòu)進(jìn)行，那為何不提出遞歸線(xiàn)和循環(huán)線(xiàn)兩個(gè)概念呢？

遞歸線(xiàn)可以認(rèn)為是遞歸遍歷的線(xiàn)性結(jié)構(gòu)，比如N皇后題目中待遍歷的N行、電話(huà)號(hào)碼字母組合題目中待遍歷的N個(gè)數(shù)字、單詞搜索題目中待遍歷的網(wǎng)格、子集題目中待遍歷的數(shù)字?jǐn)?shù)組。而遞歸點(diǎn)則是遞歸遍歷時(shí)的具體位置，比如N皇后中具體的某一行，電話(huà)號(hào)碼字母組合中具體某一個(gè)數(shù)字。

循環(huán)線(xiàn)則是某個(gè)遞歸點(diǎn)需要遍歷的幾種可能選擇。比如N皇后題目中某一行需要遍歷的N列、電話(huà)號(hào)碼字母組合題目中某一個(gè)數(shù)字對(duì)應(yīng)的需要遍歷的字母集合、單詞搜索題目中某個(gè)網(wǎng)格需要遍歷的左右上下4個(gè)鄰居格子。而循環(huán)點(diǎn)則是循環(huán)遍歷時(shí)的具體位置，比如N皇后問(wèn)題中某個(gè)具體的行的具體列。

**遞歸線(xiàn)和循環(huán)線(xiàn)相互相成。某個(gè)遞歸點(diǎn)的在循環(huán)時(shí)選定的循環(huán)點(diǎn)往往就是下一個(gè)遞歸點(diǎn)。 ** 對(duì)于單詞搜索題目，選定的循環(huán)點(diǎn)就是下一次遞歸的遞歸點(diǎn)，而對(duì)于N皇后問(wèn)題，循環(huán)點(diǎn)的選擇就不影響下一次遞歸點(diǎn)。

回溯遞歸題目一般所求都是一個(gè)集合，需要在不斷遞歸和循環(huán)時(shí)記錄選擇的遞歸點(diǎn)和循環(huán)點(diǎn)，在某個(gè)適當(dāng)?shù)臅r(shí)機(jī)將一路上記錄的遞歸點(diǎn)和循環(huán)點(diǎn)放到一個(gè)集合中。一般來(lái)說(shuō)，會(huì)用一個(gè)vector記錄每次遞歸時(shí)選擇的循環(huán)點(diǎn)(push_back)。在回溯的時(shí)候，清除當(dāng)前循環(huán)點(diǎn)(pop_back)。遍歷到下一個(gè)循環(huán)點(diǎn)，再用vector記錄之。

顯然，對(duì)于遞歸回溯題目，找到遞歸線(xiàn)和循環(huán)線(xiàn)基本上就可以認(rèn)為問(wèn)題解決了大半。這類(lèi)問(wèn)題的代碼結(jié)構(gòu)都是類(lèi)似的，一個(gè)遞歸函數(shù) + 一個(gè)for循環(huán) + 位置記錄vector。

下面通過(guò)一些題目訓(xùn)練掌握并鞏固這個(gè)思路。

顯式的遞歸循環(huán)線(xiàn)

電話(huà)號(hào)碼的字母組合

leetcode原題https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

題目描述

給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。

給出數(shù)字到字母的映射如下（與電話(huà)按鍵相同）。注意 1 不對(duì)應(yīng)任何字母。

file

例子

輸入：digits = "23"
輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

題解

數(shù)字"23"可以用于遞歸遍歷，每次遞歸就訪(fǎng)問(wèn)下一個(gè)下標(biāo)的數(shù)字，也就是數(shù)字字符串本身是遞歸線(xiàn)，而每個(gè)具體的數(shù)字則是遞歸點(diǎn)。每個(gè)數(shù)字都對(duì)應(yīng)有幾個(gè)字母，這些字母就是循環(huán)線(xiàn)。進(jìn)入到某個(gè)遞歸點(diǎn)時(shí)，就循環(huán)遍歷循環(huán)線(xiàn)上的字母。于是：

遞歸線(xiàn)：

遞歸遍歷字符串中的每個(gè)數(shù)字。

內(nèi)部循環(huán)線(xiàn)

循環(huán)遍歷遞歸點(diǎn)數(shù)字對(duì)應(yīng)的字母數(shù)組。

遞歸和內(nèi)部循環(huán)的結(jié)束條件

當(dāng)所有的數(shù)字都遞歸遍歷完成后，即可終止遞歸。循環(huán)則是每個(gè)數(shù)字的字母都遍歷一次，遍歷完成即可終止。

注意點(diǎn)：

每次遞歸是都需要記錄當(dāng)前循環(huán)選擇的值。

AC代碼

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        m_vec.clear();
        if(digits.empty())
            return m_vec;


        std::string str;
        dfs(digits, 0, str);

        return m_vec;
    }

    void dfs(const std::string &digits, int index, std::string &str)
    {
        if(index == digits.size())
        {
            m_vec.push_back(str);
            return ;
        }


        for(auto c : m_nums[digits[index]])//循環(huán)遍歷每個(gè)數(shù)字對(duì)應(yīng)的字母
        {
            str.push_back(c);//記錄本次遞歸選擇的循環(huán)值
            dfs(digits, index+1, str);
            str.pop_back();//釋放本次遞歸選擇的循環(huán)制
        }
    }


private:
    std::vector<string> m_vec;
    std::map<char, string> m_nums = { {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"},{'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"} };
};

N皇后

leetcode原題https://leetcode-cn.com/problems/n-queens/

題目描述

n 皇后問(wèn)題 研究的是如何將 n 個(gè)皇后放置在 n×n 的棋盤(pán)上，并且使皇后彼此之間不能相互攻擊。
給你一個(gè)整數(shù) n ，返回所有不同的 n 皇后問(wèn)題 的解決方案。
每一種解法包含一個(gè)不同的 n 皇后問(wèn)題 的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位。

例子

file

輸入：n = 4
輸出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解釋?zhuān)喝缟蠄D所示，4 皇后問(wèn)題存在兩個(gè)不同的解法。

題解

N皇后問(wèn)題中，遞歸線(xiàn)就是棋盤(pán)上的那N行，每個(gè)遞歸點(diǎn)的循環(huán)線(xiàn)就是該行的所有列。由于N皇后問(wèn)題中N個(gè)皇后不能相互沖突，因此在循環(huán)遍歷到某一列時(shí)，需要檢查能否選定該列。這也是稍微復(fù)雜的點(diǎn)，遍歷時(shí)判斷該點(diǎn)是否滿(mǎn)足條件。

遞歸線(xiàn)：

遞歸遍歷棋盤(pán)的每一行。

內(nèi)部循環(huán)線(xiàn)

循環(huán)遍歷遞歸行中的N列。

遞歸和內(nèi)部循環(huán)的結(jié)束條件

當(dāng)該行沒(méi)有任何一列滿(mǎn)足條件時(shí)終止遞歸；當(dāng)遞歸到最后一行時(shí)終止遞歸。

注意點(diǎn)：

循環(huán)時(shí)需要判斷循環(huán)點(diǎn)是否滿(mǎn)足N皇后的不沖突條件。

AC代碼

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        m_locations.clear();

        std::vector<int> locate;
        dfs(locate, n);

        std::vector<std::vector<std::string>> ret;
        for(auto &vec : m_locations)
        {
            std::vector<std::string> vec_str(n, std::string(n, '.'));
            for(int i = 0; i < vec.size(); ++i)
            {
                vec_str[i][vec[i]] = 'Q';
            }

            ret.push_back(std::move(vec_str));
        }

        return ret;
    }

    void dfs(std::vector<int> &locate, int n)
    {
        if(locate.size() == n)
        {
            m_locations.push_back(locate);
            return ;
        }

        for(int i = 0; i < n; ++i)
        {
            if(isValid(locate, i))
            {
                locate.push_back(i);
                dfs(locate, n);
                locate.pop_back();
            }
        }
    }

    bool isValid(const std::vector<int> &locate, int index)
    {
        //存在同一列
        if(std::find(locate.begin(), locate.end(), index) != locate.end())
            return false;

        //斜線(xiàn) x軸之差等于y軸之差就在斜線(xiàn)上
        int size = locate.size(); //這個(gè)size是index所在的y軸位置
        for(int i = 0; i < size; ++i)
        {
            int x_diff = std::abs(index - locate[i]);
            int y_diff = size - i;

            if(x_diff == y_diff)
                return false;
        }

        return true;
    }

private:
    std::vector<std::vector<int>> m_locations;
};

單詞搜索

leetcode原題https://leetcode-cn.com/problems/word-search/

題目描述

給定一個(gè) m x n 二維字符網(wǎng)格 board 和一個(gè)字符串單詞 word 。如果 word 存在于網(wǎng)格中，返回 true ；否則，返回 false 。

單詞必須按照字母順序，通過(guò)相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用。

例子

file

輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
輸出：true

題解

遞歸線(xiàn)是每一個(gè)格子，而每個(gè)遞歸點(diǎn)的循環(huán)線(xiàn)則是該格子上下左右四個(gè)鄰居。有了遞歸線(xiàn)和循環(huán)線(xiàn)，大體的代碼架子就浮現(xiàn)了。還有幾個(gè)要注意的點(diǎn)。1.單詞開(kāi)始的地方不一定是左上角的格子，可能從任意一個(gè)格子開(kāi)始；2. 每個(gè)格子需要只能走一次，因此需要記錄每個(gè)格子是否已經(jīng)走過(guò)；3. 邊上的格子的下一個(gè)遞歸點(diǎn)不能跨過(guò)邊界；3. 選擇的循環(huán)點(diǎn)就是下一次遞歸時(shí)的遞歸點(diǎn)。

遞歸線(xiàn)：

遞歸遍歷網(wǎng)格中的每個(gè)格子。

內(nèi)部循環(huán)線(xiàn)

循環(huán)遍歷遞歸點(diǎn)格子的上下左右四個(gè)鄰居。循環(huán)時(shí)需要判斷該循環(huán)點(diǎn)是否已經(jīng)走過(guò)了。

遞歸和內(nèi)部循環(huán)的結(jié)束條件

當(dāng)某個(gè)格子不符合單詞下一個(gè)字符時(shí)，終止遞歸。越出網(wǎng)格邊界時(shí)終止遞歸。

注意點(diǎn)：

如前所述

AC代碼

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.empty() || word.empty())
            return false;

        int row = board.size();
        int col = board[0].size();

        for(int i = 0; i < row; ++i)
        {
            for(int j = 0; j < col; ++j)
            {
                if(board[i][j] == word[0] && existCore(board, i, j , word, 0))
                    return true;
            }
        }

        return false;
    }


    bool existCore(std::vector<std::vector<char>> &mat, int i, int j, const std::string &word, int index)
    {
        if(mat[i][j] != word[index])
            return false;
        else if(index+1 == word.size())
            return true;


        int row = mat.size();
        int col = mat[0].size();

        char record = '#';

        //往左
        if(j > 0)
        {
            std::swap(mat[i][j], record); //標(biāo)志該格子已經(jīng)走過(guò)
            if(existCore(mat, i, j-1, word, index+1))
                return true;

            std::swap(mat[i][j], record); //復(fù)原該格子
        }

        //往右
        if(j < col-1)
        {
            std::swap(mat[i][j], record);
            if(existCore(mat, i, j+1, word, index+1))
                return true;

            std::swap(mat[i][j], record);
        }

        //往下
        if(i < row-1 )
        {
            std::swap(mat[i][j], record);
            if(existCore(mat, i+1, j, word, index+1))
                return true;

            std::swap(mat[i][j], record);
        }

        //往上
        if(i > 0 )
        {
            std::swap(mat[i][j], record);
            if(existCore(mat, i-1, j, word, index+1))
                return true;

            std::swap(mat[i][j], record);
        }

        return false;
    }
};

隱式的循環(huán)線(xiàn)

數(shù)字組合

leetcode原題https://leetcode-cn.com/problems/combinations/

題目描述

給定兩個(gè)整數(shù) n 和 k，返回范圍 [1, n] 中所有可能的 k 個(gè)數(shù)的組合。

你可以按 任何順序 返回答案。

例子

輸入：n = 4, k = 2
輸出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

題解

相對(duì)于前面的題目，本題只有一條明顯的可遞歸或者循環(huán)的線(xiàn)：1到n這n個(gè)數(shù)字。按照前面題目的經(jīng)驗(yàn)，題目給出的數(shù)組適宜作為遞歸線(xiàn)。那循環(huán)線(xiàn)是什么？看過(guò)這類(lèi)題目的讀者可能知曉的答案："選擇或者不選擇當(dāng)前的數(shù)字“ 這兩種情況。比如說(shuō)遞歸到數(shù)字3，此時(shí)既可以選擇3，也可以不選擇3。這兩種情況就是循環(huán)線(xiàn)。當(dāng)然只有兩種情況時(shí)，代碼上并不會(huì)寫(xiě)成循環(huán)的形式。但本質(zhì)就是循環(huán)線(xiàn)。

遞歸線(xiàn)：

遞歸遍歷1到n這數(shù)組中的每一個(gè)數(shù)字

內(nèi)部循環(huán)線(xiàn)

循環(huán)遍歷遞歸點(diǎn)數(shù)字的選擇和不選擇兩種情況。

遞歸和內(nèi)部循環(huán)的結(jié)束條件

當(dāng)選擇的數(shù)字達(dá)到了預(yù)設(shè)的k個(gè)時(shí)，就終止遞歸。

注意點(diǎn)：

注意剪枝，當(dāng)剩余未遞歸的數(shù)字?jǐn)?shù)量小于k時(shí)，沒(méi)必要再遞歸了。因?yàn)榧词谷x了也湊不夠k個(gè)數(shù)字。

AC代碼

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {

        m_collections.clear();

        std::vector<int> nums(n);
        std::iota(nums.begin(), nums.end(), 1);

        std::vector<int> vec;

        dfs(nums, 0, vec, k);
        return m_collections;
    }


    //vec存放已經(jīng)選定的數(shù)字，k表示還差幾個(gè)數(shù)字沒(méi)有收集
    void dfs(const std::vector<int> &nums, int index, std::vector<int> &vec, int k)
    {
        if(k == 0)
        {
            m_collections.push_back(vec);
            return ;
        }

        //剪枝。還需k個(gè)數(shù)字，但目前能提供數(shù)字都不夠k個(gè)
        if( (k > nums.size()-index) || index == nums.size() )
        {
            return ;
        }


        //因?yàn)橹挥袃煞N情況，所以沒(méi)有必要寫(xiě)成循環(huán)的形式
        dfs(nums, index+1, vec, k); //不選擇這個(gè)數(shù)字

        vec.push_back(nums[index]); //選擇這個(gè)數(shù)字
        dfs(nums, index+1, vec, k-1);
        vec.pop_back();
    }

private:
    std::vector<std::vector<int>> m_collections;
};

子集

leetcode原題https://leetcode-cn.com/problems/subsets/

題目描述

給你一個(gè)整數(shù)數(shù)組 nums ，數(shù)組中的元素 互不相同 。返回該數(shù)組所有可能的子集（冪集）。
解集 不能 包含重復(fù)的子集。你可以按 任意順序 返回解集。

例子

輸入：nums = [1,2,3]
輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

題解

這題目和前面的數(shù)字組合的類(lèi)似的。唯一不同的是就是遞歸終止條件。數(shù)字組合中，限制了不多不少只能選擇k個(gè)數(shù)字。而本題則是沒(méi)有這個(gè)限制。

遞歸線(xiàn)：

遞歸遍歷數(shù)組中的每一個(gè)數(shù)字。

內(nèi)部循環(huán)線(xiàn)

遍歷遞歸點(diǎn)數(shù)字的選擇和不選擇兩種情況。

遞歸和內(nèi)部循環(huán)的結(jié)束條件

當(dāng)遞歸完數(shù)組的最后一個(gè)元素時(shí)終止遞歸。

注意點(diǎn)：

無(wú)。

AC代碼

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        m_vec.clear();

        std::vector<int> vec;
        subSetsCore(nums, 0, vec);

        return m_vec;
    }

    void subSetsCore(const std::vector<int> &nums, int startIndex, std::vector<int> &vec)
    {
        if(startIndex == nums.size())
        {
            m_vec.push_back(vec);
            return ;
        }


         //因?yàn)橹挥袃煞N情況，所以沒(méi)有必要寫(xiě)成循環(huán)的形式
        subSetsCore(nums, startIndex+1, vec);//不選擇該數(shù)字

        vec.push_back(nums[startIndex]);
        subSetsCore(nums, startIndex+1, vec); //選擇該數(shù)字
        vec.pop_back();
    }

private:
    std::vector<std::vector<int>> m_vec;
};

全排列

leetcode原題https://leetcode-cn.com/problems/permutations/

題目描述

給定一個(gè)不含重復(fù)數(shù)字的數(shù)組 nums ，返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

例子

輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

題解

這題目的遞歸線(xiàn)比較明顯，就是遍歷數(shù)組的每個(gè)元素。循環(huán)線(xiàn)呢？選和不選？并不能滿(mǎn)足題設(shè)。第一次碰到該題目百思不得其解。后來(lái)看到題解后，wocao 還能這樣玩。對(duì)于每個(gè)遞歸點(diǎn)的循環(huán)線(xiàn)是遞歸點(diǎn)的元素和后面的元素swap一次。通過(guò)這樣不斷交換位置，實(shí)現(xiàn)不同的排序。

遞歸線(xiàn)：

遞歸遍歷對(duì)數(shù)組中的每一個(gè)數(shù)字

內(nèi)部循環(huán)線(xiàn)

循環(huán)遍歷遞歸點(diǎn)數(shù)字后面的元素，并與遞歸點(diǎn)的元素進(jìn)行交換。

遞歸和內(nèi)部循環(huán)的結(jié)束條件

當(dāng)遞歸完數(shù)組的最后一個(gè)元素時(shí)終止遞歸

注意點(diǎn)：

無(wú)

AC代碼

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        m_ret.clear();

        dfs(nums, 0);

        return m_ret;
    }

    void dfs(std::vector<int> &nums,  int startIndex)
    {
        if(startIndex == nums.size())
        {
            m_ret.push_back(nums);
            return ;
        }

        for(int i = startIndex; i < nums.size(); ++i)
        {
            std::swap(nums[i], nums[startIndex]);
            dfs(nums, startIndex+1);
            std::swap(nums[i], nums[startIndex]);
        }
    }


private:
    vector<vector<int>> m_ret;
};

隱式的遞歸和循環(huán)線(xiàn)

括號(hào)生成

leetcode原題https://leetcode-cn.com/problems/generate-parentheses/

題目描述

數(shù)字 n 代表生成括號(hào)的對(duì)數(shù)，請(qǐng)你設(shè)計(jì)一個(gè)函數(shù)，用于能夠生成所有可能的并且 有效的 括號(hào)組合。
有效括號(hào)組合需滿(mǎn)足：左括號(hào)必須以正確的順序閉合

例子

輸入：n = 3
輸出：["((()))","(()())","(())()","()(())","()()()"]

題解

一開(kāi)始會(huì)比較懵逼，遞歸線(xiàn)和循環(huán)線(xiàn)都沒(méi)有頭緒。沒(méi)有條件也要?jiǎng)?chuàng)造條件上。之前的遞歸線(xiàn)是順著一個(gè)數(shù)組、格子等一個(gè)結(jié)構(gòu)遞歸的。本題中并沒(méi)有任何一個(gè)結(jié)構(gòu)。那能不能順著次數(shù)遞歸？比如說(shuō)左括號(hào)使用次數(shù)，每使用一個(gè)左括號(hào)就遞歸一次。這個(gè)思路是不錯(cuò)，但還是有一些細(xì)節(jié)要斟酌。比如例子中的一個(gè)有效括號(hào)組合((()))，當(dāng)遞歸完3個(gè)左括號(hào)后，后面是3個(gè)右括號(hào)是怎么生成的？循環(huán)線(xiàn)？

能不能將括號(hào)的使用作為遞歸線(xiàn)？循環(huán)線(xiàn)則是某遞歸點(diǎn)下，遍歷["選擇左括號(hào)", "選擇右括號(hào)"]。也就是選擇的循環(huán)點(diǎn)就是下一次遞歸的遞歸點(diǎn)。這個(gè)和前面的單詞搜索題目類(lèi)似。

另外，這題和N皇后題目類(lèi)似，并不是循環(huán)線(xiàn)上的所有循環(huán)點(diǎn)都能選擇。需要判斷該選擇得是合法的括號(hào)順序。

遞歸線(xiàn)：

單純遞歸，沒(méi)有結(jié)構(gòu)依賴(lài)。在循環(huán)線(xiàn)上選定一個(gè)合法的循環(huán)點(diǎn)之后就作為遞歸點(diǎn)進(jìn)入下一次遞歸。

內(nèi)部循環(huán)線(xiàn)

循環(huán)遍歷["選擇左括號(hào)", "選擇右括號(hào)"]。選擇時(shí)需要檢查循環(huán)點(diǎn)是否為合法的括號(hào)順序。

遞歸和內(nèi)部循環(huán)的結(jié)束條件

當(dāng)左右括號(hào)數(shù)都為n時(shí)，終止遍歷。

注意點(diǎn)：

無(wú)

AC代碼

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        m_vec.clear();

        std::string str;
        dfs(str, n, n);
        return m_vec;
    }

    void dfs(std::string &str, int left_num, int right_num)
    {
        if(left_num == 0 && right_num == 0)
        {
            m_vec.push_back(str);
            return ;
        }

        //可以繼續(xù)放左括號(hào)
        if(left_num > 0)
        {
            str.push_back('(');
            dfs(str, left_num-1, right_num);
            str.pop_back();
        }

        //當(dāng)str中 左括號(hào)的數(shù)量大于右括號(hào)的數(shù)量，那么可以繼續(xù)往str放一個(gè)右括號(hào)。
        if(left_num < right_num) // < 號(hào)是因?yàn)槭鞘Ｓ鄶?shù)
        {
            str.push_back(')');
            dfs(str, left_num, right_num-1);
            str.pop_back();
        }


        //自然終止遞歸。
    }

private:
    std::vector<std::string> m_vec;
};

去重問(wèn)題

組合總和II

leetcode原題https://leetcode-cn.com/problems/combination-sum-ii/

題目描述

給定一個(gè)數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。
candidates 中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。
注意：解集不能包含重復(fù)的組合

例子

輸入: candidates = [10,1,2,7,6,1,5], target = 8,
輸出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

題解

這題是前面題目“組合”的變種，也是遞歸遍歷一個(gè)整數(shù)數(shù)組中選擇出一些數(shù)字。只是本題的遞歸終止條件包含了題設(shè)：選出的數(shù)字總和等于target。

另外，本題還有一個(gè)需要注意的點(diǎn)是解集中不能包含重復(fù)的組合。

遞歸線(xiàn)：

遞歸遍歷數(shù)組中的每一個(gè)數(shù)字。

內(nèi)部循環(huán)線(xiàn)

循環(huán)遍歷遞歸點(diǎn)數(shù)字的選擇和不選擇兩種情況。

遞歸和內(nèi)部循環(huán)的結(jié)束條件

當(dāng)遞歸完數(shù)組的最后一個(gè)元素時(shí)終止遞歸；當(dāng)選出的數(shù)字總和大于等于target時(shí)終止遍歷；

注意點(diǎn)：

如前所述需要避免重復(fù)組合，具體方法參考代碼注釋

AC代碼

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        m_ret.clear();

        //排序是為了后面的去重
        std::sort(candidates.begin(), candidates.end());

        std::vector<int> path;
        dfs(candidates, path, 0, target);

        return m_ret;
    }


    void dfs(const std::vector<int> &candidates, std::vector<int> &path, int start_index, int target)
    {
        if(target == 0) //滿(mǎn)足題設(shè)
        {
            m_ret.push_back(path);
            return ;
        }


        //剪枝
        if(target < 0 || start_index >= candidates.size())
            return ;



        //選擇這個(gè)元素
        path.push_back(candidates[start_index]);
        dfs(candidates, path, start_index+1, target-candidates[start_index]);
        path.pop_back();



        //不選擇start_index位置上的這個(gè)元素。不能簡(jiǎn)單不選擇就可以了。考慮[1, 2, 2, 2, 3, 4]
        //此時(shí)start_index為1。對(duì)于前面選擇這個(gè)元素，那么就是結(jié)果集中有了【1, 2】. 如果在start_index為1
        //的位置不選擇2，轉(zhuǎn)身在start_index等于2的位置就選擇了2， 那么結(jié)果集中也是【1, 2】，此時(shí)就重復(fù)了
        //因此，如果跳過(guò)了，那么就一直跳過(guò)這個(gè)值。
        for(int v = candidates[start_index++]; start_index < candidates.size() && v == candidates[start_index]; )
            ++start_index;

        dfs(candidates, path, start_index, target);

    }


private:
    std::vector<std::vector<int>> m_ret;
};

子集II

leetcode原題https://leetcode-cn.com/problems/subsets-ii/

涉及重復(fù)子集的問(wèn)題

題目描述

給你一個(gè)整數(shù)數(shù)組 nums ，其中可能包含重復(fù)元素，請(qǐng)你返回該數(shù)組所有可能的子集（冪集）。
解集 不能 包含重復(fù)的子集。返回的解集中，子集可以按 任意順序 排列。

例子

輸入：nums = [1,2,2]
輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

題解

遞歸線(xiàn)和循環(huán)線(xiàn)都比較明確，遞歸線(xiàn)就是數(shù)組。循環(huán)線(xiàn)就是選和不選遞歸點(diǎn)數(shù)字這兩種情況。要注意的是要避免重復(fù)的子集。這個(gè)避免的思路和前面題目的一致，跳過(guò)后面相同值的元素即可。

另外，本題還有一個(gè)需要注意的點(diǎn)是解集中不能包含重復(fù)的組合。

遞歸線(xiàn)：

遞歸遍歷數(shù)組中的每一個(gè)數(shù)字。

內(nèi)部循環(huán)線(xiàn)

循環(huán)遍歷遞歸點(diǎn)數(shù)字的選擇和不選擇兩種情況。

遞歸和內(nèi)部循環(huán)的結(jié)束條件

當(dāng)遞歸完數(shù)組的最后一個(gè)元素時(shí)終止遞歸；

注意點(diǎn)：

如前所述需要避免重復(fù)子集，具體方法參考代碼注釋

AC代碼

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        m_ret.clear();

        std::vector<int> vec;
        std::sort(nums.begin(), nums.end());//排序是為了后面的去重

        dfs(nums, vec, 0);

        return m_ret;
    }


    void dfs(const std::vector<int> &nums, std::vector<int> &vec, int startIndex)
    {
        if(startIndex == nums.size())
        {
            m_ret.push_back(vec);
            return ;
        }


        //選擇該元素
        vec.push_back(nums[startIndex]);
        dfs(nums, vec, startIndex+1);
        vec.pop_back();


        //不選擇該元素，那么需要跳過(guò)所有相同的元素
        int val = nums[startIndex++];
        while(startIndex < nums.size() && nums[startIndex] == val)
            ++startIndex;

        dfs(nums, vec, startIndex);
    }

private:
    std::vector<std::vector<int>> m_ret;
};

全排列II

leetcode原題https://leetcode-cn.com/problems/permutations-ii/

題目描述

給定一個(gè)可包含重復(fù)數(shù)字的序列 nums ，按任意順序 返回所有不重復(fù)的全排列。

例子

輸入：nums = [1,1,2]
輸出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

題解

這題是前面全排列的變形題，難點(diǎn)在于需要會(huì)出現(xiàn)重復(fù)的數(shù)字并且需要去重。前面的全排列解法中，需要不同對(duì)兩個(gè)位置的數(shù)字進(jìn)行swap，因此即使在一開(kāi)始做排序，后面經(jīng)過(guò)遞歸和各種swap后，各種可能的排列都會(huì)有的(畢竟這題目是全排列)。此時(shí)不能簡(jiǎn)單用前面的去重方法了。新的去重方法參考代碼中的注釋。

遞歸線(xiàn)：

遞歸遍歷對(duì)數(shù)組中的每一個(gè)數(shù)字

內(nèi)部循環(huán)線(xiàn)

循環(huán)遍歷遞歸點(diǎn)數(shù)字后面的元素，并與遞歸點(diǎn)的元素進(jìn)行交換。

遞歸和內(nèi)部循環(huán)的結(jié)束條件

當(dāng)遞歸完數(shù)組的最后一個(gè)元素時(shí)終止遞歸

注意點(diǎn)：

需要去重，具體參考代碼中的注釋

AC代碼

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        m_ret.clear();

        std::sort(nums.begin(), nums.end());

        dfs(nums, 0);
        return m_ret;
    }


    void dfs(std::vector<int> &nums, int startIndex)
    {
        if(startIndex == nums.size())
        {
            m_ret.push_back(nums);
            return ;
        }

        auto it = nums.begin();
        for(int i = startIndex; i < nums.size(); ++i)
        {
            //這里需要判斷[startIndex， i)之間是否已經(jīng)出現(xiàn)過(guò)了nums[i]。因?yàn)槿绻霈F(xiàn)過(guò)，那么它之前已經(jīng)和nums[startIndex]
            //做過(guò)了swap。此時(shí)，還將nums[i]和nums[startIndex]做swap，那么就是它之前出現(xiàn)時(shí)和startIndex做swap得到的數(shù)組
            //和i和startIndex做swap得到的數(shù)組是一致，也就是出現(xiàn)了重復(fù).
            //雖然前面有排序，但經(jīng)過(guò)N次的遞歸，swap后，再已經(jīng)面目全非，不能簡(jiǎn)單以nums[i]和nums[i-1]判斷是否相同的字符
            if(std::find(it+startIndex, it+i, nums[i]) == it+i) //[startIndex, i)之間沒(méi)有和nums[i]值相同的元素
            {
                std::swap(nums[i], nums[startIndex]);
                dfs(nums, startIndex+1);
                std::swap(nums[i], nums[startIndex]);
            }
        }
    }


private:
    std::vector<std::vector<int>> m_ret;
};

第一時(shí)間接收最新文章，請(qǐng)關(guān)注同名微信公眾號(hào)：代碼的色彩

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

LeetCode刷題套路——遞歸回溯算法

LeetCode刷題套路——遞歸回溯算法

顯式的遞歸循環(huán)線(xiàn)

電話(huà)號(hào)碼的字母組合

N皇后

單詞搜索

隱式的循環(huán)線(xiàn)

數(shù)字組合

子集

全排列

隱式的遞歸和循環(huán)線(xiàn)

括號(hào)生成

去重問(wèn)題

組合總和II

子集II

全排列II

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

LeetCode刷題套路——遞歸回溯算法

顯式的遞歸循環(huán)線(xiàn)

電話(huà)號(hào)碼的字母組合

N皇后

單詞搜索

隱式的循環(huán)線(xiàn)

數(shù)字組合

子集

全排列

隱式的遞歸和循環(huán)線(xiàn)

括號(hào)生成

去重問(wèn)題

組合總和II

子集II

全排列II

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av