【leetcode100-55到62】【回溯】八题集合

回溯专题，通用的框架在于选择-递归-撤销选择的过程，在每一个题中都有体现，就不一一重复了，只讲一讲每个题特殊的地方。

说实话好无聊啊hh回溯题怎么都长差不多啊！

【全排列】

给定一个不含重复数字的数组?nums?，返回其?所有可能的全排列?。你可以?按任意顺序?返回答案。

思路：

• 每次选一个数，并对剩下“还没被选过”的数开启递归，需要设visited数组记录每个数的被选情况，撤销时将其设为“未被选择”状态。
• 优化：将选中的数交换至数列前段，通过下标范围来标记未被选的元素，可以i简化掉visited数组。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        recursivePermute(res, nums, 0);
        return res;
    }
    void recursivePermute(vector<vector<int>>& res, vector<int>& nums,int begin) {
        if (begin == nums.size() - 1) {
            res.emplace_back(nums);
            return;
        }
        for (int i = begin; i < nums.size(); i++) {
            swap(nums[begin], nums[i]);
            recursivePermute(res, nums, begin + 1);
            swap(nums[i], nums[begin]);
        }
    }
};

【子集】

给你一个整数数组?nums?，数组中的元素?互不相同?。返回该数组所有可能的子集（幂集）。

解集?不能?包含重复的子集。你可以按?任意顺序?返回解集。

思路：

回溯最最最简单的题目，没有之一，简单到写完提交就跑，连题解都懒得去看。对任意元素考虑选还是不选两种情况，并相应地开启下一层递归就行。选择和撤销动作即为对相应位置元素的push和pop。

class Solution {
public:
    vector<vector<int>> ans;
    //vector<int> selected;
    vector<int> curArr;
    //
    void dfs(vector<int>& nums,int step){
        //出口
        if(step>=nums.size()){
            ans.push_back(curArr);
            return;
        }
        //选
        curArr.push_back(nums[step]);
        dfs(nums,step+1);
        curArr.pop_back();
        //不选
        dfs(nums,step+1);
        return;
    }
    //
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ans;
    }
};

【电话号码的字母组合】

给定一个仅包含数字?2-9?的字符串，返回所有它能表示的字母组合。答案可以按?任意顺序?返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

思路：

比常规框架多了一个数字到字母集合的映射罢了，我们用一张哈希表来解决这个步骤，然后就是对当前数字的可选字母进行遍历，对每个字母进行选择-递归-撤销选择流程。

class Solution {
public:
    string curArr;
    vector<string> ans;
    unordered_map<char, string> selection;
    void dfs(int step, string digits) {
        //数字用完了，保存答案
        if (step == digits.size()) {
            ans.push_back(curArr);
            return;
        }
        //遍历当前数字可选字母
        //选好并加入答案
        //去下一个数字
        //恢复状态
        for (char c : selection[digits[step]]) {
            curArr.push_back(c);
            dfs(step + 1, digits);
            curArr.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits.empty())
            return ans;
        selection = {{'2', "abc"}, {'3', "def"},  {'4', "ghi"}, {'5', "jkl"},
                     {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
        dfs(0, digits);
        return ans;
    }
};

【组合总和】

给你一个?无重复元素?的整数数组?candidates?和一个目标整数?target?，找出?candidates?中可以使数字和为目标数?target?的 所有?不同组合?，并以列表形式返回。你可以按?任意顺序?返回这些组合。

candidates?中的?同一个?数字可以?无限制重复被选取?。如果至少一个数字的被选数量不同，则两种组合是不同的。?

对于给定的输入，保证和为?target?的不同组合数少于?150?个。

思路：

首先排个序，让我们可以在当前总和超出target时无需再考虑更靠后的元素。本题特殊点在于，由于可以重复选取，选了某元素后我们依然会从当前元素开启下一轮递归，其他就是常规框架了。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> curArr;
    void dfs(vector<int>& candidates, int target, int start) {
        //刚好
        if (target == 0) {
            ans.push_back(curArr);
            return;
        }
        //数字超了or下标超了
        if (start == candidates.size() || target < 0)
            return;

        //选上，继续从自己开始选
        curArr.push_back(candidates[start]);
        dfs(candidates, target - candidates[start], start);
        //不选，从下一个开始选
        curArr.pop_back();
        dfs(candidates, target, start + 1);
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        //升序
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0);
        return ans;
    }
};

【括号生成】

数字?n?代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且?有效的?括号组合。

思路：

光回溯太无聊了，加了一点剪枝，或者说其实只是把本来放在函数里面的判断条件放到了开启递归之前。。

合法括号序列的判断条件可以总结为——左括号只要数量不超想加就加，任意位置之前右括号数量不能大于左括号。翻译成代码以后在任意时候进行一下“能不能加个左括号-能的话加-递归-去掉-能不能加个右括号-能的话加-递归-去掉”的流程就好了。

class Solution {
public:
    vector<string> ans;
    string curArr;
    void dfs(int l, int r) {
        //够数了
        if (l == 0 && r == 0) {
            ans.push_back(curArr);
            return;
        }
        //能放左括号，放一下
        if (l > 0) {
            curArr += '(';
            dfs(l - 1, r);
            curArr.pop_back();
        }
        //能放右括号，放一下
        if (r > l) {
            curArr += ')';
            dfs(l, r - 1);
            curArr.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        dfs(n, n);
        return ans;
    }
};

【单词搜索】

给定一个?m x n?二维字符网格?board?和一个字符串单词?word?。如果?word?存在于网格中，返回?true?；否则，返回?false?。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

思路：

本题回到了图的dfs，并套上了回溯的框架。但是有个特殊点，就是搜索的起点，不像常规一样在[0][0]了，而是需要通过遍历找到匹配的首字母才能开启。

class Solution {
public:
bool flag;
    void dfs(vector<vector<char>>& board, string word,
             vector<vector<bool>>& visit, int index, int r, int c) {
        if (index == word.size()){
            flag=true;
            return;}
        //当前格子用了，index所指的字符匹配完成
        visit[r][c] = true;
        //在四个方向找下一个匹配的
        if (0 <= r - 1 && !visit[r - 1][c] && board[r - 1][c] == word[index]) {
            dfs(board, word, visit, index + 1, r - 1, c);
        }
        if (r + 1 < board.size() && !visit[r + 1][c] &&
            board[r + 1][c] == word[index]) {
            dfs(board, word, visit, index + 1, r + 1, c);
        }
        if (0 <= c - 1 && !visit[r][c - 1] && board[r][c - 1] == word[index]) {
            dfs(board, word, visit, index + 1, r, c - 1);
        }
        if (c + 1 < board[0].size() && !visit[r][c + 1] &&
            board[r][c + 1] == word[index]) {
            dfs(board, word, visit, index + 1, r, c + 1);
        }
        //恢复状态
        visit[r][c] = false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        flag=false;
        int n=board.size(),m=board[0].size();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j]==word[0]){
                    vector<vector<bool>> visit(n,vector<bool>(m,false));
                    dfs(board,word,visit,1,i,j);
                    if(flag)return true;
                }
            }
        }
        return false;
    }
};

【分割回文串】

给你一个字符串?s，请你将?s?分割成一些子串，使每个子串都是?回文串?。返回?s?所有可能的分割方案。

回文串?是正着读和反着读都一样的字符串。

思路：

对任意元素，我们遍历以它为起点的所有可能子串，当某子串是回文串时，我们切一刀，并对切剩下的部分开启递归，结束后恢复原状并去判断下一个可能的子串。

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> curArr;
    bool isSym(string s) {
        int l = 0, r = s.size()-1;
        while (l < r) {
            if (s[l] != s[r])
                return false;
            l++;
            r--;
        }
        return true;
    }
    void dfs(string s, int start) {
        if (start == s.size()) {
            ans.push_back(curArr);
            return;
        }
        for (int i = start; i < s.size(); i++) {
            string sub = s.substr(start, i - start + 1);

            if (isSym(sub)) {
                //是回文，切一下
                curArr.push_back(sub);
                //继续切剩下的部分
                dfs(s, i + 1);
                //恢复状态
                curArr.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        dfs(s,0);
        return ans;
    }
};

【N皇后】

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n?皇后问题?研究的是如何将?n?个皇后放置在?n×n?的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数?n?，返回所有不同的?n?皇后问题?的解决方案。

每一种解法包含一个不同的?n 皇后问题?的棋子放置方案，该方案中?'Q'?和?'.'?分别代表了皇后和空位。

思路：

终于写到这个回溯经典题了。不过其实我觉得本题难度并不在于算法，它其实还是落在了常规的回溯框架里面，搞不好总结出判断皇后位置合法不合法的那几个条件都比算法本身来得难。。

我们用一个数组place记录当前已经放置的皇后，第i行的皇后放在第place[i]列。

皇后冲突可能有四种情况：行冲突，列冲突，正斜线冲突，反斜线冲突。

假设当前判断的位置坐标为（r，c）

• 我们按行顺序递增放置，所以不需要考虑行冲突
• 列冲突时，c和某个已放皇后的place[i]相同
• 观察可知，同一正斜线上的元素行号和列号之差相同，因此正斜线冲突时，r-c和某个已放皇后的i-place[i]相同
• 观察可知，同一正斜线上的元素行号和列号之和相同，因此反斜线冲突时，r+c和某个已放皇后的i+place[i]相同

对每一行，遍历可选位置，然后在符合条件的位置开启递归，并在返回后恢复原状以便进行下一个位置的判断，即可。

class Solution {
public:
    //保存当前单个解法
    //vector<string> curArr;
    //保存所有解法
    vector<vector<string>> ans;
    //保存已放皇后的位置
    vector<int> place;
    //根据位置n生成.Q串
    string makeString(int n, int queen) {
        string temp;
        for (int i = 0; i < n; i++) {
            if (i == queen)
                temp += 'Q';
            else
                temp += '.';
        }
        return temp;
    }
    //判断皇后放在某位置是否合法
    bool check(int r, int c) {
        for (int i = 0; i < r; i++) {
            if (c == place[i] || r - c == i - place[i] || r + c == i + place[i])
                return false;
        }
        return true;
    }
    // dfs
    void dfs(int n, int cur) {
        //放完了，保存当前答案
        if (cur == n) {
            vector<string> temp;
            for (int i = 0; i < n; i++) {
                temp.push_back(makeString(n, place[i]));
            }
            ans.push_back(temp);
            return;
        }
        //没放完，开始放第cur行的皇后
        for (int j = 0; j < n; j++) {
            //如果放在j列不冲突
            if (check(cur, j)) {
                place[cur] = j;
                dfs(n, cur + 1);
                // place[cur] = -1;
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        //vector<int> place(n, -1);
        for(int i=0;i<n;i++)place.push_back(-1);
        dfs(n, 0);
        return ans;
    }
};