回溯算法精讲

原理

回溯，就和深度优先遍历（DFS）类似，属于先一层到底直至到终点，如果这条路径不对，则回退一下，再继续往下搜索。

抽象地说，解决一个回溯问题，实际上就是遍历一棵决策树的过程，树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍，把叶子节点上的答案都收集起来，就能得到所有的合法答案。

基本策略属于：”深度优先遍历“ + ”状态回退“

核心框架

路径：已经做出的选择。
选择列表：当前可以做的选择。
结束条件：达到决策树底层，无法再做选择的条件。

for 属于横向遍历
递归，属于纵向遍历
这样就将整个集合全部搜索了一遍

在这里插入图片描述

void backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

做选择：将当前的选择加入到路径中，并更新选择列表和路径。
递归调用：继续向下逐层递归，如果到达决策树的底层，满足结束条件，则将当前路径加入到结果集中。
撤销选择：递归完成返回后，撤销前一步的选择，恢复状态，尝试其他选项。

核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」

回溯法主要解决什么问题？

当回溯法求解问题，我们可以尽量将问题抽象为树形结构，上文我们都说过属于深度遍历搜索 + 回退状态，所以尽可能的抽象为树结构。
回溯法就可以理解为，再集合中递归查询子集，集合大小就是抽象树的宽度，递归深度就是抽象树的深度。

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

组合问题

力扣77题：组合

思路：
第一，先抽象为一个树。

第二：找到终止条件
根据题意，当路径达到我们需要的，我们就直接终止

        if(path.size() == k){
            res.push_back(path);
            return;
        }

第三、怎么横向遍历？
直接往后一步一步挪动。

        for(int i = start; i<=n;i++){
            path.push_back(i);
            back(n,k,i+1);
            path.pop_back();
        }

该题解完整代码：

class Solution {
public:

    vector<vector<int>> res; // 最终结果
    vector<int> path;		//	每次查询的路径

    vector<vector<int>> combine(int n, int k) {
        back(n,k,1);
        // 测试输出
        for (vector<vector<int>>::iterator it = res.begin(); it != res.end(); it++) {
                for (vector<int>::iterator jt = (*it).begin(); jt != (*it).end(); jt++) {
                    cout << *jt << " ";
                }
                cout << endl;
        }
        return res;
    }
    // 回溯代码
    void back(int n,int k ,int start){
        if(path.size() == k){
            res.push_back(path);
            return;
        }
        for(int i = start; i<=n;i++){
            path.push_back(i);
            back(n,k,i+1);
            path.pop_back();
        }
    }
};

如何优化呢？就是剪枝问题了。比如就这道题，如果 N= 4， k = 4，那是不是从 2 开始后面都不行，因为不够4个数。但是我们上文代码，属于全部搜索一下。如何优化？

for (int i = start; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

力扣 216 组合总和III

这题和上题，思路基本一致，唯一修改，就是我们再遍历路径的时候，对路径上的值进行加减。直接看代码：

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

    int all = 0; // 用来记录路径上的值
    void back(int k ,int n, int start){
        if(all > n){  // 剪枝操作，此处代表后续路径都不可能会存在了
            return;
        }
        if(path.size()==k&& all == n){
            // if(all == n){
            //     res.push_back(path);
            // }
            res.push_back(path);
            return;
        }
        for(int i = start ; i<=9 - (k-path.size()) + 1 ;i++){
            all += i;   
            path.push_back(i);
            back(k,n,i+1);
           // int c = path.back();
           // path.pop_back();
           // all -= c;  // 回退也需要将他减去
           path.pop_back();
           all -= i;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        back(k,n,1);
        return res;
    }
};

力扣17.电话号码的字母组合

思路：

这道题终究还是归结于组合问题，无非事每一层树节点需要根据数字进行判断，看下图。

class Solution {
public:

    const string letterMap[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };

    vector<string> res;
    string path;

    void back(string digits ,int index){
        if(index == digits.size()){
            res.push_back(path);
            return;
        }
        int digit = digits[index] - '0';
        string letters = letterMap[digit];
        for(int i = 0 ; i< letters.size();i++){
            path.push_back(letters[i]); 
            back(digits,index+1);  // 递归处理下一层数字
            path.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0){
            return res;
        }
        
        back(digits,0);
        return res;
    }
};

力扣39. 组合总和

思路：会故意想上文216题，是不是也是存在路径值得问题？但这题与之区别是什么呢？因为这题得节点可以重复选取，我们需要怎么改变？

看代码，我们在 back得时候，是不是又从 i 节点开始得？代表我每次都可以重复选取

        for(int i = index;i<candidates.size();i++){
            path.push_back(candidates[i]);
            num += candidates[i];
            back(candidates,target,i);
            num -= candidates[i];
            path.pop_back();
        }

完整代码：

class Solution {
public:

    vector<vector<int>> res;
    vector<int>path;

    int num = 0;
    void back(vector<int> candidates,int target,int index){
        if(num > target){
            return;
        }
        if(num == target){
            res.push_back(path);
            return;
        }
        for(int i = index;i<candidates.size();i++){
            path.push_back(candidates[i]);
            num += candidates[i];
            back(candidates,target,i);
            num -= candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        for(int i = 0;i<candidates.size();i++){
            cout<<setw(4)<<candidates[i];
        }
        back(candidates,target,0);
        return res;
    }
};

力扣40.组合总和II

思路：

对于去重问题，我们得考虑，什么是树枝

根据题目，我们得看一点，集合中数据存在重复，然后每个数字只能用一次。这样我们就需要去加个判断了。
经典判断：
用来看这个数据我们处理过没有。

  // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
 // used[i - 1] == false，说明同一树层candidates[i - 1]使用过

        bool visited[candidates.size()] ;
        for(int i = 0 ;i<candidates.size();i++){
            visited[i] = false;
        }

看完整代码：

class Solution {
public:

    vector<vector<int>> res;
    vector<int>path;
    int num = 0;
    void back(vector<int> candidates,int target,int index,bool visited[]){
        if(num > target){
            return;
        }
        if(num == target){
            // // 此处比较超出时间限制
            // vector<vector<int>>::iterator it = find(res.begin(), res.end(), path);
            // if(it == res.end()){
            //     res.push_back(path);
            // }
            res.push_back(path);
            return;
        }
        for(int i = index;i<candidates.size() && (num+candidates[i])<=target;i++){
        	// 通过 visited进行去重
            // if(i>index && candidates[i] == candidates[i-1] && visited[i-1] ==){
            //     continue;
            // }
            
            // 判断同层，是否有遇到相同数字，如果遇到，则跳过，因为会重复
            if(i>index && candidates[i] == candidates[i-1] ){
                continue;
            }
            path.push_back(candidates[i]);
            visited[i] = true;
            num += candidates[i];
            back(candidates,target,i+1,visited);
            num -= candidates[i];
            visited[i] =false;
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        
        bool visited[candidates.size()] ;
        for(int i = 0 ;i<candidates.size();i++){
            visited[i] = false;
        }

        sort(candidates.begin(),candidates.end()); // 排序
        for(int i = 0;i<candidates.size();i++){
            cout<<setw(4)<<candidates[i];
        }

        back(candidates,target,0,visited);
        return res;
    }
};

组合总结

其实组合问题，最经典就是77题的组合，其他题型无非就是在此基础上加入了路径的值，或者不能重复。

重点：

怎么去重？
去什么的重？树枝上？还是同一树层？
怎么使用visited，来判断是否经历过这个节点？
  // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
 // used[i - 1] == false，说明同一树层candidates[i - 1]使用过

组合问题总结

组合问题最基础还是77题，基本都是在此基础上的衍生。

核心回溯模板如下：

    void backtracking(int n, int k, int index)
    {
        if(path.size() == k)
        {
            res.push_back(path);
            return;
        }

        for(int i = index; i<=n;i++)
        {
            path.push_back(i);
            backtracking(n,k,i+1);  // 不能重复选择
            path.pop_back();
        }
    }

当我们可以重复选择时，在递归时，就得注意一下了

backtracking(n,k,i);   // 可以重复选择

接下来就是关于去重问题了

去重分为两种：
树枝去重：used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
树层去重：used[i - 1] == false，说明同一树层candidates[i - 1]使用过

分割问题

我们先搞清楚，分割和组合得区别
比如字符串 abcdef
组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…。
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…。

131.分割回文串

怎么将切割问题转化为抽象树呢？

注意：每切一个，我们得想想还剩下什么，剩下的又怎么切？什么时候去切？
核心代码：

       for(int i = index;i<s.size();i++){
            if(ishuiwen(s,index,i)){
                string str = s.substr(index, i - index + 1);
                path.push_back(str);
                back(s,i+1);
                path.pop_back();
            }
        }

完整代码：

class Solution {
public:

    //` string substr(int pos = 0, int n = npos) const; //返回由pos开始的n个字符组成的字符串`
    vector<vector<string>> res;
    vector<string> path;

    void back(string s,int index){
        if(index >= s.size()){
            res.push_back(path);
            return;
        }

        for(int i = index;i<s.size();i++){
            if(ishuiwen(s,index,i)){
                string str = s.substr(index, i - index + 1);
                path.push_back(str);
                back(s,i+1);
                path.pop_back();
            }
        }
    }

    bool ishuiwen(string s,int index ,int c){
        for(int i = index,j = c; i<j;i++,j--){
            if(s[i] == s[j]){
                continue;
            }else{
                return false;
            }
        }
        return true;
    }
    vector<vector<string>> partition(string s) {
        back(s,0);
        return res;
    }
};

力扣93.复原IP地址

思路：
我们此处怎么去切割？是不是就等于在字符串上加个 ’.‘ 是不是就属于切割？

思路：

这个也属于分割问题
我们按照其中的 ‘.’ 数来确实是否达标了
选择代码如下

if (count > 4) return; // 超过四部分，返回
        if (index == s.size() && count == 4) { // 完全匹配四部分
            res.push_back(path.substr(0, path.length() - 1)); // 移除最后的一个点
            return;
        }

那么如何在数层排列呢？
我们可以按照点数进行循环

        for (int i = 1; i <= 3; i++) {
            if (index + i > s.size()) break; // 超出字符串长度
            string str = s.substr(index, i);
            if (isValid(str)) {
                path += str + ".";
                back(s, index + i, count + 1);
                path.erase(path.length() - i - 1, i + 1); // 回溯，移除刚添加的部分及点
            }
        }

完整代码如下：

class Solution {
public:
    vector<string> res;
    string path;
    
    void back(string s, int index, int count) {
        if (count > 4) return; // 超过四部分，返回
        if (index == s.size() && count == 4) { // 完全匹配四部分
            res.push_back(path.substr(0, path.length() - 1)); // 移除最后的一个点
            return;
        }

        for (int i = 1; i <= 3; i++) {
            if (index + i > s.size()) break; // 超出字符串长度
            string str = s.substr(index, i);
            if (isValid(str)) {
                path += str + ".";
                back(s, index + i, count + 1);
                path.erase(path.length() - i - 1, i + 1); // 回溯，移除刚添加的部分及点
            }
        }
    }

    bool isValid(const string& str) {
        if (str.size() > 1 && str[0] == '0') return false; // 防止前导零
        int num = stoi(str);
        return num <= 255;
    }
    
    vector<string> restoreIpAddresses(string s) {
        back(s, 0, 0);
        return res;
    }
};

分割问题总结

其实分割问题，还是在 77 题组合问题上的修改。
我们在详细分化一下什么是组合，什么又是分割。

组合问题
组合问题主要是在不考虑元素顺序的情况下，从一组元素中选择若干元素的所有可能方式。

元素顺序不重要：选择的元素集合 [1,2] 和 [2,1] 被认为是相同的。
不切割原数据：直接在原数据集上进行选择。

分割问题
分割问题通常是指将一个字符串或数组分割成符合特定条件的多个子部分。

考虑元素顺序：分割的段必须维持原有元素的顺序。
切割原数据：需要在原数据中按顺序选择切点。

我们给出核心模板代码：

    void backtrack(const string& s, int start) {
        if (start == s.size()) { // 如果起始位置已经到达字符串末尾
            result.push_back(path);
            return;
        }

        for (int i = start; i < s.size(); i++) {
            if (isValid(s, start, i)) { // 判断当前分割是否有效
                path.push_back(s.substr(start, i - start + 1)); // 取子串并加入路径
                backtrack(s, i + 1); // 递归调用，从下一个字符开始新的分割
                path.pop_back(); // 回溯，撤销上一步的分割
            }
        }
    }

    bool isValid(const string& s, int start, int end) {
        // 判断 s[start...end] 是否符合条件，具体实现依据问题而定
        while (start < end) {
            if (s[start] != s[end])
                return false;
            start++;
            end--;
        }
        return true;
    }

子集问题

子集问题，就是组合问题的特殊版本。
子集问题，属于集合是无序的：那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！

以示例中nums = [1,2,3]为例把求子集抽象为树型结构，如下：
在这里插入图片描述

78.子集

思路：

我们在77题，基础上进行修改，就是无序的组合

完整代码：

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

    void back(vector<int> nums,int index){
        res.push_back(path);
        if(index>=nums.size()){
            return;
        }


        for(int i = index;i<nums.size();i++){
            path.push_back(nums[i]);
            back(nums,i+1);
            path.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        // res.push_back(path);
        back(nums,0);
        return res;
    }
};

90.子集II

思路

我们先明白一点，这个子集不能是同重复的子集
是不是又回到当初的一个知识点？
判断是数层重复？还是树枝重复？

核心去重代码
我们用之前used方法进行判断：

            // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
            // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
            // 而我们要对同一树层使用过的元素进行跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }

		 // 跳过这个递归层次，防止重复
            if(i > index && nums[i] == nums[i-1] && i >= 1){
                continue;
            }

完整代码：

class Solution {
public:

    vector<vector<int>> res;
    vector<int> path;

    void back(vector<int> &nums,int index){
        res.push_back(path);
        if(index >= nums.size()){
            return;
        }

        for(int i = index;i<nums.size();i++){
            // 跳过这个递归层次，防止重复
            if(i > index && nums[i] == nums[i-1] && i >= 1){
                continue;
            }
            path.push_back(nums[i]);
            back(nums,i+1);
            path.pop_back();
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        back(nums,0);
        return res;
    }
};

排列问题

排列，是属于有序的。和前文的组合不一样。比如： [1,2] 和 [2,1] 是两个集合。
可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。
所以此时for循环如下，直接从0开始，不在需要startIndex索引了。

for (int i = 0; i < nums.size(); i++)

那如何判断，是否数组里面有的已经使用过呢？此时我们就要继续用到上述的 used 函数。

  if (used[i] == true) continue; // path里已经收录的元素，直接跳过

在这里插入图片描述

46.全排列

思路：

我们还是可以按照，77题基础代码进行修改。
我们加入判断，看看是不是使用过的。

if (used[i] == true) continue; // path里已经收录的元素，直接跳过

完整代码如下：

class Solution {
public:

    vector<vector<int>> res;
    vector<int> path;
    void back(vector<int> &nums, vector<bool>& visited){
        if(path.size() == nums.size()){
            res.push_back(path);
            return;
        }
        for(int i = 0 ; i < nums.size();i++){
            if(visited[i]== true){
                continue;
            }
            path.push_back(nums[i]);
            visited[i] = true;
            back(nums,visited);
            visited[i] = false;
            path.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> visited(nums.size(),false);
        back(nums,visited);
        return res;
    }
};

47.全排列 II

思路：

对比于上一个题，我们区别是什么？就是不重复的全排列。
不重复，第一时间想到的就是，树枝去重？还是数层去重呢？
此题，就是树层的去重。

核心代码如下：

if (used[i]) continue; // 如果当前元素已使用，则跳过
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // 跳过重复元素

完整代码如下：

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> results;
        vector<int> path;
        vector<bool> used(nums.size(), false); // 标记是否使用过该元素
        sort(nums.begin(), nums.end()); // 排序，以便跳过重复元素
        backtrack(nums, path, used, results);
        return results;
    }

    void backtrack(const vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& results) {
        if (path.size() == nums.size()) {
            results.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) continue; // 如果当前元素已使用，则跳过
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // 跳过重复元素
            
            path.push_back(nums[i]);
            used[i] = true;
            backtrack(nums, path, used, results);
            path.pop_back();
            used[i] = false;
        }
    }
};

排列问题总结

回溯法解决排列问题的原理：

选择：从一组数中选出一个元素作为排列的一部分，并标记该元素以避免重复使用。
约束：在选择下一个元素时，必须确保它尚未在当前排列中使用过（对于不包含重复元素的数组）。
目标：当排列达到数组的长度时，说明找到了一个可能的解决方案。

核心代码模板

#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        backtrack(nums, path, used, res);
        return res;
    }

    void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& res) {
        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;
            backtrack(nums, path, used, res); // 继续递归填下一个数
            path.pop_back(); // 撤销选择
            used[i] = false; // 撤销选择
        }
    }
};

棋盘问题

51. N皇后

思路：

第一个想法是，如何抽象为一个树？
这种类型就是属于网格树

我们要写出判断是否符合要求的位置：

    bool isCanreach(int row,int col ,int n){
        // 同列
        for(int i = 0; i < row; i++){
            if(path[i][col] == 'Q'){
                return false;
            }
        }

        // 左上
        for(int i = row-1,j = col-1; i>=0&&j>=0; i--,j--){
            if(path[i][j] == 'Q'){
                return false;
            }
        }

        // 右上
        for(int i = row - 1, j = col+1; i>=0 && j<n; i--,j++){
            if(path[i][j] == 'Q'){
                return false;
            }
        }
        return true;
    }

再写出回溯部分代码：

    void back(int n,int row){
        if(row == n){
            res.push_back(path);
            return ;
        }

        for(int col = 0 ; col < n; col++){
            if(isCanreach(row,col,n)){
                path[row][col] = 'Q';
                back(n,row+1);
                path[row][col] = '.';
            }
        }
    }

完整代码如下：

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

    void back(int n,int row){
        if(row == n){
            res.push_back(path);
            return ;
        }

        for(int col = 0 ; col < n; col++){
            if(isCanreach(row,col,n)){
                path[row][col] = 'Q';
                back(n,row+1);
                path[row][col] = '.';
            }
        }
    }

    bool isCanreach(int row,int col ,int n){
        // 同列
        for(int i = 0; i < row; i++){
            if(path[i][col] == 'Q'){
                return false;
            }
        }

        // 左上
        for(int i = row-1,j = col-1; i>=0&&j>=0; i--,j--){
            if(path[i][j] == 'Q'){
                return false;
            }
        }

        // 右上
        for(int i = row - 1, j = col+1; i>=0 && j<n; i--,j++){
            if(path[i][j] == 'Q'){
                return false;
            }
        }
        return true;
    }

    vector<vector<string>> solveNQueens(int n) {
        path.resize(n, string(n, '.'));
        back(n,0);
        return res;
    }
};

37. 解数独

思路：
我们还是得先想想这种问题，如何抽象为一个抽象树呢？

判断棋盘是否合法有如下三个维度：

同行是否重复
同列是否重复
9宫格里是否重复

    bool isCanreach(vector<vector<char>>& board,int row,int col,char c){
        for(int i = 0; i<9;i++){
            if(board[row][i] == c){
                return false;
            }
            if(board[i][col] == c){
                return false;
            }
            // 3*3方格
            if(board[3*(row/3)+i/3][3*(col/3)+i%3] == c){
                return false;
            }
        }
        return true;
    }

一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！

    bool back(vector<vector<char>>& board){
        for(int i = 0;i<9;i++){
            for(int j = 0;j<9;j++){
                if(board[i][j] == '.'){
                    for(char c = '1' ; c<='9';c++){
                        if(isCanreach(board,i,j,c)){
                            board[i][j] = c;
                            if(back(board)){
                                return true;
                            }
                            // 回溯
                            board[i][j] = '.';
                        }
                    }
                    // 代表所有数字都不行
                    return false;
                }
            }
        }
        return true;
    }

完整代码：

class Solution {
public:

    //vector<vector<char>> res;

    bool back(vector<vector<char>>& board){
        for(int i = 0;i<9;i++){
            for(int j = 0;j<9;j++){
                if(board[i][j] == '.'){
                    for(char c = '1' ; c<='9';c++){
                        if(isCanreach(board,i,j,c)){
                            board[i][j] = c;
                            if(back(board)){
                                return true;
                            }
                            // 回溯
                            board[i][j] = '.';
                        }
                    }
                    // 代表所有数字都不行
                    return false;
                }
            }
        }
        return true;
    }

    bool isCanreach(vector<vector<char>>& board,int row,int col,char c){
        for(int i = 0; i<9;i++){
            if(board[row][i] == c){
                return false;
            }
            if(board[i][col] == c){
                return false;
            }
            // 3*3方格
            if(board[3*(row/3)+i/3][3*(col/3)+i%3] == c){
                return false;
            }
        }
        return true;
    }

    void solveSudoku(vector<vector<char>>& board) {
        back(board);
    }
};