最近做了一些回溯法题目，整理一下便于未来复习刷题。

回溯法定义

回溯法（英语：backtracking）是暴力搜索法中的一种。

对于某些计算问题而言，回溯法是一种可以找出所有（或一部分）解的一般性算法，尤其适用于约束满足问题（在解决约束满足问题时，我们逐步构造更多的候选解，并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解，转而测试其他的部分候选解）。

在经典的教科书中，八皇后问题展示了回溯法的用例。（八皇后问题是在标准国际象棋棋盘中寻找八个皇后的所有分布，使得没有一个皇后能攻击到另外一个。）

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

• 找到一个可能存在的正确的答案
• 在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

使用情景

1. 当我们需要得到某个问题的全部解时
2. 通过枚举所有可能性找出问题的答案时

贪心算法利用局部最优解的思想找到的答案有可能不是整体最优的，这是也需要使用回溯法来找到答案。

主要思想

1. 寻找递归树，找到状态变量(回溯函数的参数)
2. 根据题意，确立结束条件
3. 找准选择列表(与函数参数相关),与第一步紧密关联※
4. 判断是否需要剪枝
5. 作出选择，递归调用，进入下一层
6. 撤销选择

一般思路

void backtrace(int index){
    if(index==end){ //出口条件
      //将当前解放入解集中
    }
    for(int i=0;i<N;i++){ //每个位置的可能取值
      //保存当前状态
      //将当前元素放入解中
      backtrace(index+1);//进入下一层
      //恢复状态，回溯
    }
}

分类

最近做了一些题，回溯法内部有一些比较有特点的题目。对于有不同特点的题目的解法也有一些不同。

回溯类型	leetcode例题
子集、组合	子集、子集 II、组合、组合总和、组合总和 II
全排列	全排列、全排列 II、字符串的全排列、字母大小写全排列
搜索	解数独、单词搜索、N皇后、分割回文串、二进制手表

子集、组合

子集

选择出来的解不能相互重复，与解内的顺序无关。

求子集就是一个典型的例子。

78. 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解集中的解都不重复，而且解中的元素与顺序无关（比如 [1,2,3]和[1,3,2]属于同一个解，与顺序无关）。

这种解的特性就属于子集。对于这类问题的思路为：

void backtrace(int start){
    if(start==end){ //出口条件
      //将当前解放入解集中
    }
    for(int i=start;i<N;i++){
      //保存当前状态
      //将当前元素放入解中
      backtrace(i+1);//选择不能重复，每次只能选下一个元素之后的元素，若包含当前元素则这个地方为i
      //恢复状态，回溯
    }
}

①寻找递归树，找到状态变量(回溯函数的参数)

熟悉了可以在脑海中有个大概的图，这个步骤是用来对问题形成结构

矩形内为待选元素，箭头上的数字为当前的选择的解。菱形内每行代表一个解，可以看到菱形中的所有解就是解集。

②根据题意，确立结束条件

递归的每一步都产生一个解，所以没有出口限定条件。

 void backtrace(int start, vector<int>& nums, vector<int> list) {
     ans.push_back(list);
     
  
  }

③找准选择列表(与函数参数相关),与第一步紧密关联※

这个选择列表就是解中当前位置可能出现的情况

void backtrace(int start, vector<int>& nums, vector<int> list) {
     ans.push_back(list);
 
     for(int i=start;i<nums.size();i++){
        
     }
  }

nums.size()就是解可能出现的情况范围。

④判断是否需要剪枝

不需要剪枝，每个产生的解都符合条件，可以放入解集里。

⑤作出选择，递归调用，进入下一层

void backtrace(int start, vector<int>& nums, vector<int> list) {
     ans.push_back(list);
     
     for(int i=start;i<nums.size();i++){
        list.push_back(nums[i]);
        backtrace(i+1,nums,list);
     
     }
  }

⑥撤销选择

void backtrace(int start, vector<int>& nums, vector<int> list) {
     ans.push_back(list);
     
     for(int i=start;i<nums.size();i++){
        list.push_back(nums[i]);
        backtrace(i+1,nums,list);
        list.pop_back();
     }
  }

全部代码

class Solution {
 public:
  vector<vector<int>> ans;
  vector<vector<int>> subsets(vector<int>& nums) {
     vector<int> list;
     backtrace(0,nums,list);
     return ans;
  }

  void backtrace(int start, vector<int>& nums, vector<int> list) {
     ans.push_back(list);
     
     for(int i=start;i<nums.size();i++){
        list.push_back(nums[i]);
        backtrace(i+1,nums,list);
        list.pop_back();
     }
  }
};

我们再看一个需要剪枝的例子。

子集剪枝

剪枝的目的是去掉我们不需要的解或者加快求解速度。

这里我们介绍一个给输入的去重的方法，虽然上面说的求子集方法得出的答案是没有重复的，但当输入有重复时，结果依然会有重复。通过例题你就会看到这种情况。

90. 子集 II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

寻找递归树，找到状态变量(回溯函数的参数)

观察上图不难发现，应该去除当前选择列表中与上一个数重复的那个数。如“2，2”这个选择列表，第二个“2”是最后重复的，应该去除这个“2”引出的分支。注意：应该先对数组进行排序！！！让相同的元素放在一起，比如[1,5,8,5,1]，排序后[1,1,5,5,8]这样就能检测到当前元素是不是和上一个元素相同！除了排序，其实使用hash表也可以做到（一会演示）。

其它步骤相同，我们直接看剪枝这一块。

 void backtrace(int start, vector<int>& nums, vector<int> list) {
    ans.push_back(list);

    for (int i = start; i < nums.size(); i++) {
        if(i>start&&nums[i]==nums[i-1]) continue;
     //剪枝，注意i>start保证若待选矩形里只有一个2，但是nums[i-1]中已经为2。这种情况的2是必选的，因为这不属于重复的情况。
      list.push_back(nums[i]);
      backtrace(i + 1, nums, list);
      list.pop_back();
    }
  }

组合

组合是回溯中比较常见的应用，它和子集很相似，因为组合中的解像子集一样不能重复（与解中元素顺序无关）。下面举个例子。

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 
示例 1：

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]

示例 2：

输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
 

①寻找递归树，找到状态变量(回溯函数的参数)

递归树就不画了，这个递归树很大。但我们需要找准递归树中关键的元素：每次递归的选择，出口条件，剪枝条件。由于本题可以有重复元素，每次选择是所有元素。而不是从没选过的元素开始选。

②根据题意，确立结束条件

 void backtrace(int sum, vector<int>& vec, int index) {
    if (index == nums.size()) {
      return; //到最后一个元素，本次没有找到解
    }
    if (sum == goal) { //寻找到一个解
      ans.push_back(vec);
      return;
    }

  }

③找准选择列表(与函数参数相关),与第一步紧密关联※

可以有重复元素

 void backtrace(int sum, vector<int>& vec, int index) {
    if (index == nums.size()) {
      return;
    }
    if (sum == goal) {
      ans.push_back(vec);
      return;
    }

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

④判断是否需要剪枝

不需要剪枝，每个产生的解都符合条件，可以放入解集里。

⑤作出选择，递归调用，进入下一层

 void backtrace(int sum, vector<int>& vec, int index) {
    if (index == nums.size()) {
      return;
    }
    if (sum == goal) {
      ans.push_back(vec);
      return;
    }

    for (int i = 0; i < nums.size(); i++) {
      vec.push_back(nums[i]);
      sum+=nums[i];
      backtrace(sum, vec, i+1);
    }
  }

⑥撤销选择

 void backtrace(int sum, vector<int>& vec, int index) {
    if (index == nums.size()) {
      return;
    }
    if (sum == goal) {
      ans.push_back(vec);
      return;
    }

    for (int i = 0; i < nums.size(); i++) {
      vec.push_back(nums[i]);
      sum+=nums[i];
      backtrace(sum, vec, i+1);
      vec.pop_back();
      sum-=nums[i];
    }
  }

组合类的变形有很多，在实际应用中很少有这样有明显是组合题目，一般是具有组合的特点。

总结：

子集，组合类题目最大的特点在于这一句

backtrace(i+1);

i+1表示从下一个选择开始回溯，这样再进行选择时就不会和之前选过的元素顺序重复，符合子集，组合的特点。

全排列

全排列就是求n个元素能组成多少个不同顺序的解

一般代码模板

  void backtrace(int index, vector<int>& output, vector<bool>& visited,
           vector<int>& nums) {
    if (index == nums.size()) {  //输出
      ans.push_back(output);
      return;
    }
    for (int i = 0     //从0开始
    ; i < nums.size(); i++) {
      if () { //剪枝
        
        visited[i] = true; //去除重复
        backtrace(index + 1, output, visited, nums);
        //回溯
        visited[i] = false;
        output.pop_back();
      }
    }
  }

和子集，组合问题的区别在于，全排列的解中元素的下标从0开始，也就是对于每一个已经选择的元素，下一个元素仍可能是之前没有选过的元素，这里需要一个数组标记。而子集，组合下一个元素只能是当前元素后面的元素。

46. 全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

题解代码，因为很好理解就不一步一步介绍了。

class Solution {
 public:
  vector<vector<int>> ans;
  vector<vector<int>> permute(vector<int>& nums) {
    vector<int> output;
    vector<bool> visited(nums.size(), false);
    dfs(0, output, visited, nums);
    return ans;
  }
  void dfs(int index, vector<int>& output, vector<bool>& visited,
           vector<int>& nums) {
    if (index == nums.size()) {
      ans.push_back(output);
      return;
    }
    for (int i = 0
    ; i < nums.size(); i++) {
      if (visited[i]==false) {
        output.push_back(nums[i]);
        visited[i] = true;
        dfs(index + 1, output, visited, nums);
        visited[i] = false;
        output.pop_back();
      }
    }
  }
};

对于排列问题还有一种解法，使用交换的方式。

class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};

搜索

八皇后问题是一个典型的搜索问题，通过剪枝来排除掉不符合要求的答案，暴力解题。

八皇后问题大家也比较了解，这里我们换一个例题。

401. 二进制手表

我之前写过讲解

https://www.cztcode.com/2020/401-binary-watch/

其实关于搜索问题，需要按照题中的问题进行分析。但是枚举核心思想都是使用回溯，通过列举所有可能的情况找到其中的解。需要注意的是，回溯法时间复杂度一般较高，如果可以使用动态规划等其它算法可以优先使用。