回溯 - lbyxiaolizi's blog

回溯是在 DFS 的基础上加入了选择与撤销，本质还是 DFS ，写的时候需要多注意的是临界条件与选、递归、撤的套路

直接从题开始吧

46. 全排列

全排列应该是最简单的回溯题了，代码几乎是回溯的模板了

class Solution {
public:
    vector<vector<int>> res;
    vector<bool> used;
    vector<int> path;
    void dfs(vector<int>& nums){
        if(path.size()==nums.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(used[i]){
                continue;
            }
            path.push_back(nums[i]);
            used[i]=true;
            dfs(nums);
            path.pop_back();
            used[i]=false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        used.resize(nums.size(),false);
        dfs(nums);
        return res;
    }
};

78. 子集

本题和全排列不一样的点在于边界条件不需要要求 path 排满，只要有元素就可以算一种答案；并且我们不需要也不应当引入顺序不同的相同组合，所以引入了 start 参数来控制

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void dfs(vector<int>& nums,int start){
        res.push_back(path);
        for(int i=start;i<nums.size();i++){
            path.push_back(nums[i]);
            dfs(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums,0);
        return res;
    }
};

17. 电话号码的字母组合

本题和全排列稍有相像，需要做一个数字和字母的 mapping

由于这里要的也是组合，不看顺序，一个数字还对应多个字母，所以我们用一个参数 index 来表示到了第几个数字。

class Solution {
public:
    vector<string> res;
    string path;
    vector<string> mapping = {
        "",     // 0
        "",     // 1
        "abc",  // 2
        "def",  // 3
        "ghi",  // 4
        "jkl",  // 5
        "mno",  // 6
        "pqrs", // 7
        "tuv",  // 8
        "wxyz"  // 9
    };

    void dfs(string digits,int index){
        if(index==digits.size()){
            res.push_back(path);
            return;
        }
        int digit=digits[index]-'0';
        string letters=mapping[digit];
        for(char c:letters){
            path.push_back(c);
            dfs(digits,index+1);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return {};
        dfs(digits,0);
        return res;
    }
};

39. 组合总和

本题要求从给定组合的数字中凑出指定答案，返回方案的列表，其中同一个数字可以被多次选择

这题看上去比前面的吓人多了，实际上和子集几乎一模一样，唯一区别的同一个数字可被多次选择只需要修改递归时的参数 start 让本位的也可传进去即可

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    int start;
    void dfs(vector<int>& candidates,int target,int start,int sum){
        if(sum==target){
            res.push_back(path);
            return;
        }
        if(sum>target) return;
        for(int i=start;i<candidates.size();i++){
            path.push_back(candidates[i]);
            dfs(candidates,target,i,sum+candidates[i]);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates,target,0,0);
        return res;
    }
};

22. 括号生成

虽然但是，每次看到这种括号匹配的题都被吓死，但是实际上并不是很难，又不是手搓正则（x

本题不用考虑什么复杂的括号到底应该怎么放，用递归的情况下只要抓住几个条件即可：

左括号必须在右括号左边
右括号的数量永远不大于左括号的数量
左括号的数量最终等于 n

根据这几个边界条件进行括号放置和压栈即可

class Solution {
public:
    vector<string> res;
    string path;
    void dfs(int n,int left,int right){
        if(left == n && right == n){
            res.push_back(path);
            return;
        }
        if(left<n){
            path.push_back('(');
            dfs(n,left+1,right);
            path.pop_back();
        }
        if(right<left){
            path.push_back(')');
            dfs(n,left,right+1);
            path.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        dfs(n,0,0);
        return res;
    }
};

79. 单词搜索

一个 m*n 的棋盘格里装满字母要求匹配给定单词，看上去有点像前缀树（

用回溯来写依旧需要注意几个临界条件：坐标不能超出棋盘以外、单词的字母不匹配、正确字母与单词的总长一致；由于一个字母只能选择一次，所以在选中后将其改掉，回溯时在改回即可

class Solution {
public:
    int m,n;
    bool dfs(vector<vector<char>>& board,string word,int x,int y,int k){
        if(x<0||y<0||x>=m||y>=n) return false;
        if(board[x][y]!=word[k]) return false;
        if(k==word.size()-1) return true;

        char temp=board[x][y];
        board[x][y]='#';
        bool found=(dfs(board,word,x,y+1,k+1)||dfs(board,word,x+1,y,k+1) || dfs(board,word,x,y-1,k+1)|| dfs(board,word,x-1,y,k+1));
        board[x][y]=temp;
        return found;
    }
    bool exist(vector<vector<char>>& board, string word) {
        m=board.size();
        n=board[0].size();

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(dfs(board,word,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
};

后续还可通过单词长度超出可选择字母数量等进行剪枝优化

131. 分割回文串

依旧是从前往后不重复选择，所以是熟悉的多加一个 start 参数。

新增的一点要求就是判断子串是不是回文串，要将不是回文串的部分进行剪枝

class Solution {
public:
    vector<string> path;
    vector<vector<string>> res;

    bool isPalindrome(string& s,int left,int right){
        while(left<right){
            if(s[left]!=s[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    void dfs(string s,int start){
        if(start==s.size()){
            res.push_back(path);
            return;
        }

        for(int i=start;i<s.size();i++){
            if(!isPalindrome(s,start,i)){
                continue;
            }
            path.push_back(s.substr(start,i-start+1));
            dfs(s,i+1);
            path.pop_back();
        }
    }

    vector<vector<string>> partition(string s) {
        dfs(s,0);
        return res;
    }
};

51. N 皇后

啊，是 N 皇后，我们没救了（诶这不是 dp 题吗

要求检查的是同行、同列、左对角线、右对角线是否有 Q 存在，如果没有则可以在该行放置一个 Q，否则不可。

按照此要求进行回溯即可

class Solution {
public:
    vector<vector<string>> res;
    bool isValid(vector<string>& board,int row,int col,int n){
        for(int i=0;i<row;i++){
            if(board[i][col]=='Q'){
                return false;
            }
        }
        for(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--){
            if(board[i][j]=='Q'){
                return false;
            }
        }
        for(int i=row-1,j=col+1;i>=0 && j<n;i--,j++){
            if(board[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }

    void dfs(vector<string>& board,int row,int n){
        if(row==n){
            res.push_back(board);
            return;
        }
        for(int col=0;col<n;col++){
            if(!isValid(board,row,col,n)){
                continue;
            }
            board[row][col]='Q';
            dfs(board,row+1,n);
            board[row][col]='.';
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n,string(n,'.'));
        dfs(board,0,n);
        return res;
    }
};

lbyxiaolizi's blog

回溯