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

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

比如N皇后問題捌刮，它每次遞歸時，就進入到下一行做一些邏輯處理舒岸。而在每一行時绅作，都會循環(huán)遍歷每一列，判斷本行該列的元素是否滿足條件蛾派。又比如電話號碼的字母組合問題俄认，每遞歸一次就進入到下一個數(shù)字，然后遍歷該數(shù)字對應的字母列表洪乍。其他問題也類似眯杏，但會有一定的變形。

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

遞歸線可以認為是遞歸遍歷的線性結(jié)構(gòu)巷波，比如N皇后題目中待遍歷的N行萎津、電話號碼字母組合題目中待遍歷的N個數(shù)字、單詞搜索題目中待遍歷的網(wǎng)格抹镊、子集題目中待遍歷的數(shù)字數(shù)組锉屈。而遞歸點則是遞歸遍歷時的具體位置，比如N皇后中具體的某一行髓考，電話號碼字母組合中具體某一個數(shù)字部念。

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

**遞歸線和循環(huán)線相互相成榜贴。某個遞歸點的在循環(huán)時選定的循環(huán)點往往就是下一個遞歸點。 ** 對于單詞搜索題目妹田，選定的循環(huán)點就是下一次遞歸的遞歸點唬党，而對于N皇后問題，循環(huán)點的選擇就不影響下一次遞歸點鬼佣。

回溯遞歸題目一般所求都是一個集合驶拱，需要在不斷遞歸和循環(huán)時記錄選擇的遞歸點和循環(huán)點，在某個適當?shù)臅r機將一路上記錄的遞歸點和循環(huán)點放到一個集合中晶衷。一般來說蓝纲，會用一個vector記錄每次遞歸時選擇的循環(huán)點(push_back)。在回溯的時候晌纫，清除當前循環(huán)點(pop_back)税迷。遍歷到下一個循環(huán)點，再用vector記錄之锹漱。

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

下面通過一些題目訓練掌握并鞏固這個思路砂心。

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

電話號碼的字母組合

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

題目描述

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

給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母纺涤。

file

例子

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

題解

數(shù)字"23"可以用于遞歸遍歷译暂，每次遞歸就訪問下一個下標的數(shù)字，也就是數(shù)字字符串本身是遞歸線撩炊，而每個具體的數(shù)字則是遞歸點外永。每個數(shù)字都對應有幾個字母，這些字母就是循環(huán)線拧咳。進入到某個遞歸點時伯顶，就循環(huán)遍歷循環(huán)線上的字母。于是：

遞歸線：

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

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

循環(huán)遍歷遞歸點數(shù)字對應的字母數(shù)組祭衩。

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

當所有的數(shù)字都遞歸遍歷完成后灶体，即可終止遞歸。循環(huán)則是每個數(shù)字的字母都遍歷一次掐暮，遍歷完成即可終止蝎抽。

注意點：

每次遞歸是都需要記錄當前循環(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)遍歷每個數(shù)字對應的字母
        {
            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 皇后問題 研究的是如何將 n 個皇后放置在 n×n 的棋盤上路克，并且使皇后彼此之間不能相互攻擊樟结。
給你一個整數(shù) n ，返回所有不同的 n 皇后問題 的解決方案精算。
每一種解法包含一個不同的 n 皇后問題 的棋子放置方案瓢宦，該方案中 'Q' 和 '.' 分別代表了皇后和空位。

例子

file

輸入：n = 4
輸出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解釋：如上圖所示灰羽，4 皇后問題存在兩個不同的解法刁笙。

題解

N皇后問題中，遞歸線就是棋盤上的那N行谦趣，每個遞歸點的循環(huán)線就是該行的所有列疲吸。由于N皇后問題中N個皇后不能相互沖突，因此在循環(huán)遍歷到某一列時前鹅，需要檢查能否選定該列摘悴。這也是稍微復雜的點，遍歷時判斷該點是否滿足條件舰绘。

遞歸線：

遞歸遍歷棋盤的每一行蹂喻。

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

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

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

當該行沒有任何一列滿足條件時終止遞歸捂寿；當遞歸到最后一行時終止遞歸口四。

注意點：

循環(huán)時需要判斷循環(huá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;

        //斜線 x軸之差等于y軸之差就在斜線上
        int size = locate.size(); //這個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/

題目描述

給定一個 m x n 二維字符網(wǎng)格 board 和一個字符串單詞 word 秦陋。如果 word 存在于網(wǎng)格中蔓彩，返回 true ；否則驳概，返回 false 赤嚼。

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

例子

file

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

題解

遞歸線是每一個格子稚照，而每個遞歸點的循環(huán)線則是該格子上下左右四個鄰居蹂空。有了遞歸線和循環(huán)線俯萌，大體的代碼架子就浮現(xiàn)了。還有幾個要注意的點上枕。1.單詞開始的地方不一定是左上角的格子绳瘟，可能從任意一個格子開始；2. 每個格子需要只能走一次姿骏，因此需要記錄每個格子是否已經(jīng)走過糖声；3. 邊上的格子的下一個遞歸點不能跨過邊界；3. 選擇的循環(huán)點就是下一次遞歸時的遞歸點分瘦。

遞歸線：

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

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

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

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

當某個格子不符合單詞下一個字符時悦施，終止遞歸。越出網(wǎng)格邊界時終止遞歸去团。

注意點：

如前所述

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); //標志該格子已經(jīng)走過
            if(existCore(mat, i, j-1, word, index+1))
                return true;

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

        //往右
        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)線

數(shù)字組合

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

題目描述

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

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

例子

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

題解

相對于前面的題目昼汗，本題只有一條明顯的可遞歸或者循環(huán)的線：1到n這n個數(shù)字。按照前面題目的經(jīng)驗鬼雀，題目給出的數(shù)組適宜作為遞歸線顷窒。那循環(huán)線是什么？看過這類題目的讀者可能知曉的答案："選擇或者不選擇當前的數(shù)字“ 這兩種情況源哩。比如說遞歸到數(shù)字3鞋吉，此時既可以選擇3，也可以不選擇3励烦。這兩種情況就是循環(huán)線谓着。當然只有兩種情況時，代碼上并不會寫成循環(huán)的形式坛掠。但本質(zhì)就是循環(huán)線赊锚。

遞歸線：

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

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

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

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

當選擇的數(shù)字達到了預設的k個時却音，就終止遞歸改抡。

注意點：

注意剪枝矢炼，當剩余未遞歸的數(shù)字數(shù)量小于k時系瓢，沒必要再遞歸了。因為即使全選了也湊不夠k個數(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表示還差幾個數(shù)字沒有收集
    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個數(shù)字，但目前能提供數(shù)字都不夠k個
        if( (k > nums.size()-index) || index == nums.size() )
        {
            return ;
        }


        //因為只有兩種情況骗绕，所以沒有必要寫成循環(huán)的形式
        dfs(nums, index+1, vec, k); //不選擇這個數(shù)字

        vec.push_back(nums[index]); //選擇這個數(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/

題目描述

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

例子

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

題解

這題目和前面的數(shù)字組合的類似的撤缴。唯一不同的是就是遞歸終止條件刹枉。數(shù)字組合中，限制了不多不少只能選擇k個數(shù)字屈呕。而本題則是沒有這個限制微宝。

遞歸線：

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

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

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

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

當遞歸完數(shù)組的最后一個元素時終止遞歸蟋软。

注意點：

無。

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 ;
        }


         //因為只有兩種情況嗽桩，所以沒有必要寫成循環(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/

題目描述

給定一個不含重復數(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]]

題解

這題目的遞歸線比較明顯棺耍，就是遍歷數(shù)組的每個元素。循環(huán)線呢种樱？選和不選蒙袍？并不能滿足題設。第一次碰到該題目百思不得其解嫩挤。后來看到題解后害幅，wocao 還能這樣玩。對于每個遞歸點的循環(huán)線是遞歸點的元素和后面的元素swap一次岂昭。通過這樣不斷交換位置以现，實現(xiàn)不同的排序。

遞歸線：

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

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

循環(huán)遍歷遞歸點數(shù)字后面的元素约啊，并與遞歸點的元素進行交換邑遏。

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

當遞歸完數(shù)組的最后一個元素時終止遞歸

注意點：

無

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)線

括號生成

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

題目描述

數(shù)字 n 代表生成括號的對數(shù)，請你設計一個函數(shù)恰矩，用于能夠生成所有可能的并且 有效的 括號組合记盒。
有效括號組合需滿足：左括號必須以正確的順序閉合

例子

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

題解

一開始會比較懵逼，遞歸線和循環(huán)線都沒有頭緒外傅。沒有條件也要創(chuàng)造條件上纪吮。之前的遞歸線是順著一個數(shù)組俩檬、格子等一個結(jié)構(gòu)遞歸的。本題中并沒有任何一個結(jié)構(gòu)碾盟。那能不能順著次數(shù)遞歸棚辽？比如說左括號使用次數(shù)，每使用一個左括號就遞歸一次屈藐。這個思路是不錯，但還是有一些細節(jié)要斟酌熙尉。比如例子中的一個有效括號組合((()))估盘，當遞歸完3個左括號后，后面是3個右括號是怎么生成的骡尽？循環(huán)線遣妥？

能不能將括號的使用作為遞歸線？循環(huán)線則是某遞歸點下攀细，遍歷["選擇左括號", "選擇右括號"]箫踩。也就是選擇的循環(huán)點就是下一次遞歸的遞歸點。這個和前面的單詞搜索題目類似谭贪。

另外境钟，這題和N皇后題目類似，并不是循環(huán)線上的所有循環(huán)點都能選擇俭识。需要判斷該選擇得是合法的括號順序慨削。

遞歸線：

單純遞歸，沒有結(jié)構(gòu)依賴套媚。在循環(huán)線上選定一個合法的循環(huán)點之后就作為遞歸點進入下一次遞歸缚态。

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

循環(huán)遍歷["選擇左括號", "選擇右括號"]。選擇時需要檢查循環(huán)點是否為合法的括號順序堤瘤。

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

當左右括號數(shù)都為n時玫芦，終止遍歷。

注意點：

無

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ù)放左括號
        if(left_num > 0)
        {
            str.push_back('(');
            dfs(str, left_num-1, right_num);
            str.pop_back();
        }

        //當str中 左括號的數(shù)量大于右括號的數(shù)量本辐，那么可以繼續(xù)往str放一個右括號桥帆。
        if(left_num < right_num) // < 號是因為是剩余數(shù)
        {
            str.push_back(')');
            dfs(str, left_num, right_num-1);
            str.pop_back();
        }


        //自然終止遞歸。
    }

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

去重問題

組合總和II

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

題目描述

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

例子

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

題解

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

另外地梨，本題還有一個需要注意的點是解集中不能包含重復的組合菊卷。

遞歸線：

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

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

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

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

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

注意點：

如前所述需要避免重復組合万细，具體方法參考代碼注釋

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_ret.push_back(path);
            return ;
        }


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



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



        //不選擇start_index位置上的這個元素扑眉。不能簡單不選擇就可以了±党考慮[1, 2, 2, 2, 3, 4]
        //此時start_index為1腰素。對于前面選擇這個元素，那么就是結(jié)果集中有了【1, 2】. 如果在start_index為1
        //的位置不選擇2雪营，轉(zhuǎn)身在start_index等于2的位置就選擇了2弓千， 那么結(jié)果集中也是【1, 2】，此時就重復了
        //因此献起，如果跳過了洋访，那么就一直跳過這個值。
        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/

涉及重復子集的問題

題目描述

給你一個整數(shù)數(shù)組 nums 谴餐，其中可能包含重復元素姻政，請你返回該數(shù)組所有可能的子集（冪集）。
解集 不能 包含重復的子集岂嗓。返回的解集中汁展，子集可以按 任意順序 排列。

例子

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

題解

遞歸線和循環(huán)線都比較明確厌殉，遞歸線就是數(shù)組食绿。循環(huán)線就是選和不選遞歸點數(shù)字這兩種情況。要注意的是要避免重復的子集公罕。這個避免的思路和前面題目的一致炫欺，跳過后面相同值的元素即可。

另外熏兄，本題還有一個需要注意的點是解集中不能包含重復的組合品洛。

遞歸線：

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

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

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

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

當遞歸完數(shù)組的最后一個元素時終止遞歸桥状；

注意點：

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

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();


        //不選擇該元素硝清，那么需要跳過所有相同的元素
        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/

題目描述

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

例子

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

題解

這題是前面全排列的變形題芦拿，難點在于需要會出現(xiàn)重復的數(shù)字并且需要去重士飒。前面的全排列解法中查邢，需要不同對兩個位置的數(shù)字進行swap，因此即使在一開始做排序酵幕，后面經(jīng)過遞歸和各種swap后扰藕，各種可能的排列都會有的(畢竟這題目是全排列)。此時不能簡單用前面的去重方法了芳撒。新的去重方法參考代碼中的注釋邓深。

遞歸線：

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

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

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

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

當遞歸完數(shù)組的最后一個元素時終止遞歸

注意點：

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

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)過了nums[i]舌菜。因為如果出現(xiàn)過萌壳，那么它之前已經(jīng)和nums[startIndex]
            //做過了swap。此時日月，還將nums[i]和nums[startIndex]做swap袱瓮，那么就是它之前出現(xiàn)時和startIndex做swap得到的數(shù)組
            //和i和startIndex做swap得到的數(shù)組是一致，也就是出現(xiàn)了重復.
            //雖然前面有排序山孔，但經(jīng)過N次的遞歸懂讯，swap后，再已經(jīng)面目全非台颠，不能簡單以nums[i]和nums[i-1]判斷是否相同的字符
            if(std::find(it+startIndex, it+i, nums[i]) == it+i) //[startIndex, 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;
};

第一時間接收最新文章褐望，請關(guān)注同名微信公眾號：代碼的色彩

最后編輯于：2021.11.08 21:41:32

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市串前，隨后出現(xiàn)的幾起案子瘫里，更是在濱河造成了極大的恐慌，老刑警劉巖荡碾，帶你破解...
沈念sama閱讀 212,884評論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件谨读，死亡現(xiàn)場離奇詭異，居然都是意外死亡坛吁，警方通過查閱死者的電腦和手機劳殖，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,755評論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來拨脉，“玉大人哆姻，你說我怎么就攤上這事∶蛋颍” “怎么了矛缨？”我有些...
開封第一講書人閱讀 158,369評論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長。經(jīng)常有香客問我箕昭，道長灵妨，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 56,799評論 1贊 285
?港島之戀（遺憾婚禮）
正文為了忘掉前任落竹，我火速辦了婚禮泌霍，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘筋量。我一直安慰自己烹吵，他們只是感情好碉熄，可當我...
茶點故事閱讀 65,910評論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布桨武。她就那樣靜靜地躺著，像睡著了一般锈津。火紅的嫁衣襯著肌膚如雪呀酸。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 50,096評論 1贊 291
城市分裂傳說
那天琼梆，我揣著相機與錄音性誉，去河邊找鬼。笑死茎杂，一個胖子當著我的面吹牛，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播锅论，決...
沈念sama閱讀 39,159評論 3贊 411
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼糠爬，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了刽脖？” 一聲冷哼從身側(cè)響起羞海，我...
開封第一講書人閱讀 37,917評論 0贊 268
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎曲管，沒想到半個月后却邓，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 44,360評論 1贊 303
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡院水，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 36,673評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年腊徙，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片檬某。...
茶點故事閱讀 38,814評論 1贊 341
活死人
序言：一個原本活蹦亂跳的男人離奇死亡撬腾，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出橙喘，到底是詐尸還是另有隱情时鸵，我是刑警寧澤，帶...
沈念sama閱讀 34,509評論 4贊 334
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站饰潜，受9級特大地震影響初坠，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜彭雾，卻給世界環(huán)境...
茶點故事閱讀 40,156評論 3贊 317
男人毒藥：我在死后第九天來索命
文/蒙蒙一碟刺、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧薯酝，春花似錦半沽、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,882評論 0贊 21
一樁弒父案者填，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至做葵，卻和暖如春占哟，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背酿矢。一陣腳步聲響...
開封第一講書人閱讀 32,123評論 1贊 267
情欲美人皮
我被黑心中介騙來泰國打工榨乎，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人瘫筐。一個月前我還...
沈念sama閱讀 46,641評論 2贊 362
代替公主和親
正文我出身青樓蜜暑，卻偏偏與公主長得像，于是被迫代替她去往敵國和親策肝。傳聞我的和親對象是個殘疾皇子肛捍，可洞房花燭夜當晚...
茶點故事閱讀 43,728評論 2贊 351

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

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

電話號碼的字母組合

N皇后

單詞搜索

隱式的循環(huán)線

數(shù)字組合

子集

全排列

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

括號生成

去重問題

組合總和II

子集II

全排列II

推薦閱讀更多精彩內(nèi)容