Skip to main content

7-回溯算法

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

回溯是递归的副产品，只要有递归就会有回溯。

1.回溯法的效率​

​ 因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

2.回溯法解决的问题​

回溯法，一般可以解决如下几种问题：

  • 组合问题：N个数里面按一定规则找出k个数的集合

  • 切割问题：一个字符串按一定规则有几种切割方式

  • 子集问题：一个N个数的集合里有多少符合条件的子集

  • 排列问题：N个数按一定规则全排列，有几种排列方式

  • 棋盘问题：N皇后，解数独等等

3.如何理解回溯法​

回溯法解决的问题都可以抽象为树形结构

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

4.回溯法模板​

1.回溯函数模板返回值以及参数

在回溯算法中，我的习惯是函数起名字为backtracking，回溯算法中函数返回值一般为void。

再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

void backtracking(参数)

2.回溯函数终止条件

既然是树形结构，就知道遍历树形结构一定要有终止条件。所以回溯也有要终止条件。

什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

所以回溯函数终止条件伪代码如下：

if (终止条件) {
    存放结果;
    return;
}

3.回溯搜索的遍历过程

在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

回溯函数遍历过程伪代码如下：

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。backtracking这里自己调用自己，实现递归。

大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

分析完过程，回溯算法模板框架如下：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

5.组合问题：​

  • 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个.....。
  • 判断结束的方法：一般结果集满足条件结束

77. 组合​

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> now;
        function<void(int)> backtracking = [&](int start)
        {
            if(now.size() == k)
            {
                res.push_back(now);
                return;
            }
            for(int i = start; i <= n ;i++)
            {
                now.push_back(i);
                backtracking(i + 1);
                now.pop_back();
            }
        };
        backtracking(1);
        return res;
    }
};

216. 组合总和 III​

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> now;
        function<void(int,int)> backtracking = [&](int start, int sum)
        {
            if(now.size() == k)
            {
                if(sum == n) res.push_back(now);
                return;
            }
            for(int i = start; i <= 9 ;i++)
            {
                now.push_back(i);
                backtracking(i + 1,sum + i);
                now.pop_back();
            }
        };
        backtracking(1,0);
        return res;
    }
};

17. 电话号码的字母组合​

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits == "") return {};
        string maps[] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        vector<string> res;
        string now;
        function<void(int)> backtracking = [&](int start)
        {
            if(digits.size() == start)
            {
                res.push_back(now);
                return;
            }
            for(int i = 0; i < maps[digits[start] - '0'].size() ;i++)
            {
                now.push_back(maps[digits[start] - '0'][i]);
                backtracking(start + 1);
                now.pop_back();
            }
        };
        backtracking(0);
        return res;
    }
};

39. 组合总和​

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

40. 组合总和 II​

注意要点：

数层上的去重操作

1.需要对原始数组进行排序

2.初始化一个used数组，对树层去重

3.如果for循环到此上一个used[i-1]为false，并且这个元素等于上一个元素，则这个就是重复

  • used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
  • used[i - 1] == false，说明同一树层candidates[i - 1]使用过
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> now;
        sort(candidates.begin(),candidates.end());
        vector<bool> used(candidates.size(),false);
        function<void(int,int)> backtracking = [&](int start, int sum)
        {
            if(sum >= target)
            {
                if(sum == target) res.push_back(now);
                return;
            }
            for(int i = start; i <  candidates.size();i++)
            {
                if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) continue;
                now.push_back(candidates[i]);
                used[i] = true;
                backtracking(i + 1,sum + candidates[i]);
                used[i] = false;
                now.pop_back();
            }
        };
        backtracking(0,0);
        return res;
    }
};

6.切割问题：​

131. 分割回文串​

  • 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段.....。
  • 判断结束的方法：一般start == num.size()结束

在for (int i = startIndex; i < s.size(); i++)循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。

class Solution {
    bool Isvalid(string &s)
    {
        string p = s;
        reverse(p.begin(),p.end());
        return p == s;
    }
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> now;
        function<void(int)> backtracking = [&](int start)
        {
            if(start == s.size())
            {
                res.push_back(now);
                return;
            }
            for(int i = start; i < s.size() ;i++)
            {
                string sub = s.substr(start,i - start + 1);
                if(Isvalid(sub)) 
                {
                    now.push_back(sub);
                    backtracking(i + 1);
                    now.pop_back();
                }
            }
        };
        backtracking(0);
        return res;
    }
};

93. 复原 IP 地址​

class Solution {
    bool Isvalid(string &s)
    {
        if(s == "") return false;
        int p = stoi(s);
        if(to_string(p).size() != s.size() || p > 255) return false;
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        function<void(int,string,int)> backtracking = [&](int start ,string now,int count)
        {
            if(count >= 4)
            {
                if(s.size() == start) 
                {
                    now.pop_back();
                    res.push_back(now);
                }
                return;
            }
            for(int i = start; i <  s.size() && i - start + 1 <= 3;i++)
            {
                string sub = s.substr(start,i - start + 1);
                if(Isvalid(sub)) backtracking(i + 1,now + sub +".",count+1);
            }
        };
        backtracking(0,"",0);
        return res;
    }
};

22. 括号生成​

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        function<void(int,int,int,string)> genchar = [&](int left , int right,int count,string now)
        {
            if(left > n || right > n) return;
            if(count == n * 2)
            {
                res.push_back(now);
                return;
            }
            if(left >= right) genchar(left + 1,right,count + 1,now + '(');
            genchar(left,right + 1,count + 1,now + ')');
        };
        genchar(0,0,0,"");
        return res;
    }
};

140. 单词拆分 II​

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        vector<string> res;
        unordered_set<string> uset(wordDict.begin(),wordDict.end());
        function<void(int,string)> dfs = [&](int start,string temp){
            if(start == s.size())
            {
                res.push_back(temp);
                return;
            }
            for(int i = start;i < s.size();i++)
            {
                string sub = s.substr(start,i - start + 1);
                if(uset.find(sub) != uset.end())
                {
                    if(start == 0) dfs(i + 1,sub);
                    else dfs(i + 1,temp+" " + sub);
                }
            }
        };
        dfs(0,"");
        return res;
    }
};

7.子集问题​

78. 子集​

因为是遍历所有结果，所有所有情况都要收集

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

90. 子集 II​

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<bool> used(nums.size(),false);
        vector<vector<int>> res;
        vector<int> now;
        function<void(int)> backtracking = [&](int start)
        {
            res.push_back(now);
            for(int i = start; i <  nums.size();i++)
            {
                if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
                used[i] = true;
                now.push_back(nums[i]);
                backtracking(i + 1);
                now.pop_back();
                used[i] = false;
            }
        };
        backtracking(0);
        return res;
    }
};

491. 递增子序列​

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> now;
        
        function<void(int)> backtracking = [&](int start)
        {
            if(now.size() >= 2)res.push_back(now);
            unordered_set<int> uset;
            for(int i = start; i <  nums.size();i++)
            {
                if(uset.find(nums[i]) != uset.end()) continue;
                if(now.empty() || now.back() <= nums[i])
                {
                    uset.insert(nums[i]);
                    now.push_back(nums[i]);
                    backtracking(i + 1);
                    now.pop_back();
                }
            }
        };
        backtracking(0);
        return res;
    }
};

8.排列问题​

46. 全排列​

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

47. 全排列 II​

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> now;
        sort(nums.begin(),nums.end());
        vector<bool> used(nums.size(),false);
        function<void(int)> backtracking = [&](int start)
        {
            if(now.size() == nums.size())
            {
                res.push_back(now);
                return;
            }
            for(int i = 0; i <  nums.size();i++)
            {
                if(used[i] || i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
                used[i] = true;
                now.push_back(nums[i]);
                backtracking(i + 1);
                now.pop_back();
                used[i] = false;
            }
        };
        backtracking(0);
        return res;
    }
};

9.棋盘问题​

51. N 皇后​

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> now(n,string(n,'.'));
        vector<vector<string>> res;
        function<bool(int , int)> isValid = [&](int row , int col){
            for(int i = 0;i < n ;i++)
                if(now[row][i] == 'Q' || now[i][col] == 'Q') return false;
            int l1 = row, l2 = col;
            while(l1 - 1 >= 0 && l2 - 1 >= 0)
            {
                l1--;
                l2--;
            }
            while(l1 < n && l2 < n)
            {
                if(now[l1++][l2++] == 'Q') return false;
            }

            l1 = row, l2 = col;
            while(l1 - 1 >= 0 && l2 + 1 < n)
            {
                l1--;
                l2++;
            }
            while(l1 < n && l2 >= 0)
            {
                if(now[l1++][l2--] == 'Q') return false;
            }
            return true;
        };


        function<void(int)> backtracking = [&](int start){
            if(start == n) 
            {
                res.push_back(now);
                return;
            }
            for(int i = 0; i < n;i++)
            {
                if(isValid(start,i))
                {
                    now[start][i] = 'Q';
                    backtracking(start + 1);
                    now[start][i] = '.';
                }
            }
        };
        backtracking(0);
        return res;
    }
};

37. 解数独​

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        function<bool(int , int ,char)> isValid = [&](int row , int col ,char num){
            for(int i = 0; i < 9; i++)
                if(board[i][col] == num || board[row][i] == num) return false;
            int l1 = row / 3 , l2 = col / 3;
            for(int i = 0;i < 3;i++)
                for(int j = 0;j < 3;j++)
                    if(board[l1 * 3 + i][l2 * 3 + j] == num) return false;
            return true;
        };
        function<bool()> backtracking = [&](){
            for(int i = 0; i < 9 ;i++)
            {
                for(int j = 0; j < 9;j++)
                {
                    if(board[i][j] == '.')
                    {
                        for(char a = '1';a <= '9';a++)
                        {
                            if(isValid(i,j,a)) 
                            {
                                board[i][j] = a;
                                bool r = backtracking();
                                if(r) return true;
                                board[i][j] = '.';
                            }
                        }
                        return false;
                    }
                }
            }
            return true;
        };
        backtracking();
    }
};

10.其余搜索类问题​

698. 划分为k个相等的子集***​

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(),nums.end(),0);
        if(sum % k != 0 || nums.size() < k) return false;
        vector<int> buckets(k , sum / k);
        sort(nums.rbegin(),nums.rend()); // 从大到小排序
        function<bool(int)> dfs = [&](int index){
            if(index >= nums.size()) return true;//如果把数字都分完了
            for(int i = 0; i < buckets.size();i++)
            {
                if(buckets[i] < nums[index]) continue;//如果当前数字大于桶的容量
                if(i > 0 && buckets[i] == buckets[i - 1]) continue; //剪枝
                buckets[i] -= nums[index];
                if(dfs(index + 1)) return true;
                buckets[i] += nums[index];
            }
            return false;
        };
        return dfs(0);
    }
};

473. 火柴拼正方形​

class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        int sum = accumulate(matchsticks.begin(),matchsticks.end(),0);
        if(sum % 4 != 0 || matchsticks.size() < 4) return false;
        int lenth = sum / 4;

        //从大到小排序
        sort(matchsticks.rbegin(),matchsticks.rend());
        if(matchsticks[0] > lenth) return false;
        //回溯算法 - bucket表示边长 -- 不能超过lenth
        int bucket[4] = {0,0,0,0};

        function<bool(int)> dfs = [&](int pos){
            if(pos == matchsticks.size()) return true;
            
            for(int i = 0; i < 4; i++)
            {
                if(i > 0 && bucket[i] == bucket[i - 1]) continue;
                if(bucket[i] + matchsticks[pos] <= lenth)
                {
                    bucket[i] += matchsticks[pos];
                    bool r = dfs(pos + 1);
                    if(r) return true;
                    bucket[i] -= matchsticks[pos];
                }
            }
            return false;
        };
        return dfs(0);
    }
};

526. 优美的排列*​

class Solution {
public:
    int countArrangement(int n) {
        vector<vector<int>> dicts(n + 1);
        for(int i = 1; i <= n;i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(i % j == 0 || j % i == 0) 
                {
                    dicts[i].push_back(j);
                }
            }
        }
            
        
        vector<int> used(n + 1, false);
        int res = 0;
        function<void(int)> dfs = [&](int index){
            if(index == n + 1) 
            {
                res++;
                return;
            }
            for(int i : dicts[index])
            {
                if(used[i]) continue;
                used[i] = true;
                dfs(index + 1);
                used[i] = false;
            }
        };
        dfs(1);
        return res;
    }
};

679. 24 点游戏​

class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        vector<double> digits;
        for (int num : nums) {
            digits.push_back((double)num);
        }
        return backTracking(digits);
    }

    bool backTracking(vector<double> digits) {
        int n = digits.size();
        if (n == 1) {
            return abs(digits[0] - 24) < 0.001;
        }
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                vector<double> newDigits;
                for (int k = 0; k < n; k++) {
                    if (k == i || k == j) continue;
                    newDigits.push_back(digits[k]);
                }
                // 标识变量isValid初始为 false，默认会执行||后面的递归。
                // 一旦某个递归返回真，isValid就变为真，由于||的短路特性，后面的递归不会执行
                bool valid = false;
                // 加法
                newDigits.push_back(digits[i] + digits[j]);
                valid = valid || backTracking(newDigits);
                newDigits.pop_back();
                // 减法
                newDigits.push_back(digits[i] - digits[j]);
                valid = valid || backTracking(newDigits);
                newDigits.pop_back();
                newDigits.push_back(digits[j] - digits[i]);
                valid = valid || backTracking(newDigits);
                newDigits.pop_back();
                // 乘法
                newDigits.push_back(digits[i] * digits[j]);
                valid = valid || backTracking(newDigits);
                newDigits.pop_back();
                // 除法
                if (digits[j] != 0) {
                    newDigits.push_back(digits[i] / digits[j]);
                    valid = valid || backTracking(newDigits);
                    newDigits.pop_back();
                }
                if (digits[i] != 0) {
                    newDigits.push_back(digits[j] / digits[i]);
                    valid = valid || backTracking(newDigits);
                    newDigits.pop_back();
                }
                if (valid) return true;
            }
        }
        return false;
    }
};

332. 重新安排行程**​

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string,map<string,int>> umap;
        for(auto x: tickets) umap[x[0]][x[1]]++;
        vector<string> res;
        res.push_back("JFK");
        function<bool()> backtracking = [&](){
            if(res.size() == tickets.size() + 1) return true;
            for(auto &mp: umap[res.back()])
            {
                if(mp.second > 0)
                {
                    mp.second--;
                    res.push_back(mp.first);
                    if(backtracking()) return true;
                    res.pop_back();
                    mp.second++;
                }
            }
            return false;
        };
        backtracking();
        return res;
    }
};

980. 不同路径 III​

class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        //回溯
        vector<vector<bool>> visited(grid.size(),vector<bool>(grid[0].size()));
        pair<int,int> start;
        int zeroCnt = 0;//找到zero个数
        for(int i = 0; i < grid.size();i++)
        {
            for(int j = 0; j < grid[0].size();j++)
            {
                if(grid[i][j] == 0) zeroCnt++;
                if(grid[i][j] == 1) 
                {
                    zeroCnt++;
                    start = {i,j};
                    grid[i][j] = 0;
                }
            }
        }
        int res = 0 ,temp = 0;
        function<void(int,int)> dfs = [&](int i, int j){
            if( visited[i][j] || grid[i][j] == -1) return;
            if(grid[i][j] == 2)
            {
                if(zeroCnt == temp) res++;
                return;
            }
            visited[i][j] = true;
            temp++;
            if(i > 0) dfs(i - 1,j);
            if(j > 0) dfs(i,j - 1);
            if(i < grid.size() - 1) dfs(i + 1,j);
            if(j < grid[0].size() - 1) dfs(i,j + 1);
            visited[i][j] = false;
            temp--;
        };
        dfs(start.first,start.second); //从1开始
        return res;
    }
};

1219. 黄金矿工​

class Solution {
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        int maxv = 0, tsum = 0;
        function<void(int ,int)> dfs = [&](int i ,int j){
            if(i >= grid.size() || j >= grid[0].size() || j < 0 || i < 0 || !grid[i][j]) return;
            int temp = grid[i][j];
            tsum += temp;
            maxv = max(maxv, tsum);
            grid[i][j] = 0;
            dfs(i + 1,j);
            dfs(i - 1,j);
            dfs(i,j + 1);
            dfs(i,j - 1);
            grid[i][j] = temp;
            tsum -= temp;
        };
        
        for(int i = 0; i < grid.size();i++)
        {
            for(int j = 0; j < grid[0].size();j++)
            {
                if(grid[i][j] > 0)dfs(i,j);
            }
        }
        return maxv;
    }
};

967. 连续差相同的数字​

class Solution {
public:
    vector<int> numsSameConsecDiff(int n, int k) {
        //回溯
        vector<int> res;
        string temp;
        unordered_set<int> uset;
        function<void(int,int)> dfs = [&](int pos,int start){
            if(start < 0|| start > 9) return;
            if(temp.size() == n)
            {
                if(temp[0] != '0' && uset.count(stoi(temp)) == 0)res.push_back(stoi(temp));
                uset.insert(stoi(temp));
                return;
            }
            temp.push_back('0' + start);
            if(start + k <= 9) dfs(pos + 1,start + k);
            if(start - k >= 0) dfs(pos + 1,start - k);
            temp.pop_back();

        };
        for(int i = 1; i <= 9; i++)dfs(0,i);
        return res;
    }
};