1、回溯算法理论知识

回溯算法理论基础

题目分类大纲如下：
image.png
可以配合我的B站视频：带你学透回溯算法（理论篇）(opens new window)一起学习！

什么是回溯法
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
在二叉树系列中，我们已经不止一次，提到了回溯，例如二叉树：以为使用了递归，其实还隐藏着回溯(opens new window)。
回溯是递归的副产品，只要有递归就会有回溯。
所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数。

回溯法的效率
回溯法的性能如何呢，这里要和大家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。
因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢？
因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。
此时大家应该好奇了，都什么问题，这么牛逼，只能暴力搜索。

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

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

相信大家看着这些之后会发现，每个问题，都不简单！
另外，会有一些同学可能分不清什么是组合，什么是排列？
组合是不强调元素顺序的，排列是强调元素顺序。
例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。
记住组合无序，排列有序，就可以了。

如何理解回溯法
回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
这块可能初学者还不太理解，后面的回溯算法解决的所有题目中，我都会强调这一点并画图举相应的例子，现在有一个印象就行。

回溯法模板
这里给出Carl总结的回溯算法模板。
在讲二叉树的递归(opens new window)中我们说了递归三部曲，这里我再给大家列出回溯三部曲。

  • 回溯函数模板返回值以及参数

在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。
回溯算法中函数返回值一般为void。
再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
但后面的回溯题目的讲解中，为了方便大家理解，我在一开始就帮大家把参数确定下来。
回溯函数伪代码如下：

  1. void backtracking(参数)
  • 回溯函数终止条件

既然是树形结构，那么我们在讲解二叉树的递归(opens new window)的时候，就知道遍历树形结构一定要有终止条件。
所以回溯也有要终止条件。
什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
所以回溯函数终止条件伪代码如下：

  1. if (终止条件) {
  2.     存放结果;
  3.     return;
  4. }
  • 回溯搜索的遍历过程

在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
如图：
image.png
注意图中，我特意举例集合大小和孩子的数量是相等的！
回溯函数遍历过程伪代码如下：

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

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
分析完过程，回溯算法模板框架如下：

  1. void backtracking(参数) {
  2.     if (终止条件) {
  3.         存放结果;
  4.         return;
  5.     }
  7.     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
  8.         处理节点;
  9.         backtracking(路径，选择列表); // 递归
  10.         回溯，撤销处理结果
  11.     }
  12. }

这份模板很重要，后面做回溯法的题目都靠它了！
如果从来没有学过回溯算法的录友们，看到这里会有点懵，后面开始讲解具体题目的时候就会好一些了，已经做过回溯法题目的录友，看到这里应该会感同身受了。

总结
本篇我们讲解了，什么是回溯算法，知道了回溯和递归是相辅相成的。
接着提到了回溯法的效率，回溯法其实就是暴力查找，并不是什么高效的算法。
然后列出了回溯法可以解决几类问题，可以看出每一类问题都不简单。
最后我们讲到回溯法解决的问题都可以抽象为树形结构（N叉树），并给出了回溯法的模板。
今天是回溯算法的第一天，按照惯例Carl都是先概述一波，然后在开始讲解具体题目，没有接触过回溯法的同学刚学起来有点看不懂很正常，后面和具体题目结合起来会好一些。

2、组合问题

77. 组合 - 力扣（LeetCode）

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。
image.png
如此我们才遍历完图中的这棵树。
for循环每次从startIndex开始遍历，然后用path保存取到的节点i。

  1. class Solution{
  2. public:
  3.     vector<vector<int>> result;        // 存放符合条件结果的集合
  4.     vector<int> path;                // 用来存放符合条件结果
  5.     void backTrcking(int n, int k, int startIndex){        // startIndex，下一层递归搜索的起始位置
  6.         if(path.size() == k){
  7.             result.push_back(path);
  8.             return;
  9.         }
  10.         for(int i = startIndex; i <= n, i++){
  11.             path.back_back(i);                // 处理节点 
  12.             backTracking(n, k, i + 1);        // 递归，纵向遍历
  13.             path.pop_back();                // 回溯，撤销处理的节点
  14.         }
  15.     }
  16. public:
  17.     vector<vector<int>> combine(int n, int k){
  18.         result.clear();        // 可以不写
  19.         path.clear();        // 可以不写
  20.         backTrcking(n, k, 1);
  21.         return result;
  22.     }
  23. };

注意：整个遍历的过程是：先纵向遍历，再横向遍历。如图
image.png

3、组合（优化）

继承上一题的问题：77. 组合- 力扣（LeetCode）

来举一个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。 在第二层for循环，从元素3开始的遍历都没有意义了。
这么说有点抽象，如图所示：
image.png
图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。
所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
注意代码中i，就是for循环里选择的起始位置。

接下来看一下优化过程如下：

  1. 已经选择的元素个数：path.size();
  2. 还需要的元素个数为: k - path.size();
  3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

  1. class Solution {
  2. public:
  3.     vector<vector<int>> result;         // 存放符合条件的结果集
  4.     vector<int> path;                   // 存放当前符合条件的当前结果
  5.     void backTracking(int n, int k, int startIndex){    // startIndex，下一层递归搜索的起始位置
  6.         if(path.size() == k){
  7.             result.push_back(path);
  8.             return;
  9.         }
  10.         for(int i = startIndex; i <= n-(k-path.size())+1; i++){   // 剪枝优化
  11.             path.push_back(i);
  12.             backTracking(n, k, i + 1);          // 进入递归，纵向遍历
  13.             path.pop_back();                    // 回溯，撤销处理的结点
  14.         }
  15.     }
  16.     vector<vector<int>> combine(int n, int k) {
  17.         result.clear();         // 可以不写
  18.         path.clear();           // 可以不写
  19.         backTracking(n, k, 1);
  20.         return result;
  21.     }
  22. };

剪枝总结
本篇我们准对求组合问题的回溯法代码做了剪枝优化，这个优化如果不画图的话，其实不好理解，也不好讲清楚。
所以我依然是把整个回溯过程抽象为一棵树形结构，然后可以直观的看出，剪枝究竟是剪的哪里。

4、组合总和III

216. 组合总和III - 力扣（LeetCode）

思路
这道题和上面的组合问题几乎是一样的，不同点就是把树的宽度换成了9，k还是树的深度。

  1. class Solution {
  2. public:
  3.     vector<vector<int>> result;     // 保存符合条件的结果集
  4.     vector<int> path;               // 保存符合当前条件的结果
  5.     int sum = 0;                    // 用sum来记录path.size()==3时的和，使得只需遍历一次就行了
  6.     void backTracking(int k, int n, int startIndex){    // startIndex下一次递归的起始位置
  7.         if(path.size() == k){
  8.             if(sum == n) result.push_back(path);
  9.             return;
  10.         }
  11.         for(int i = startIndex; i <= 9 - (k - path.size()) + 1; i++){  // for循环横向遍历 & 9-(k-path.size())+1 剪枝优化
  12.             sum += i;
  13.             path.push_back(i);
  14.             backTracking(k, n, i + 1);  // 递归，纵向遍历
  15.             path.pop_back();
  16.             sum -= i;
  17.         }
  18.     }
  20.     vector<vector<int>> combinationSum3(int k, int n) {
  21.         result.clear();        // 可以不写
  22.         path.clear();        // 可以不写
  23.         backTracking(k, n, 1);
  24.         return result;
  25.     }
  26. };

5、电话号码的字母组合

17. 电话号码的字母组合 - 力扣（LeetCode）

思路
从示例上来说，输入”23”，最直接的想法就是两层for循环遍历了吧，正好把组合的情况都输出了。
如果输入”233”呢，那么就三层for循环，如果”2333”呢，就四层for循环…….
大家应该感觉出和77.组合(opens new window)遇到的一样的问题，就是这for循环的层数如何写出来，此时又是回溯法登场的时候了。

理解本题后，要解决如下三个问题：

  1. 数字和字母如何映射
  2. 两个字符就两个for循环，三个字符就三个for循环，以此类推，然后发现代码根本就写不出来
  3. 输入 1、#、* 按键等等异常情况

image.png

C++代码如下：

  1. class Solution{
  2. private:
  3.     const string letterMap[10]{
  4.         "",         // 0
  5.         "",         // 1
  6.         "abc",      // 2
  7.         "def",      // 3
  8.         "ghi",      // 4
  9.         "jkl",      // 5
  10.         "mno",      // 6
  11.         "pqrs",     // 7
  12.         "tuv",      // 8
  13.         "wxyz",     // 9
  14.     };
  16. public:
  17.     vector<string> result;        // 存储符合条件的结果集
  18.     string path;                // 存储当前遍历的结果集
  19.     void backTracking(const string& digits, int index){    // index，，记录遍历的第几个数字，就是用来遍历digits的
  20.         if(index == digits.size()){
  21.             result.push_back(path);
  22.             return;
  23.         }
  24.         int digit = digits[index] - '0';        // 将index指向的数字转为int
  25.         string letters = letterMap[digit];        // 取数字对应的字符集
  26.         for(int i = 0; i < letters.size(); i++){
  27.             path.push_back(letters[i]);            // 处理
  28.             backTracking(digits, index + 1);    // 递归，注意index+1，下一层要处理下一个数字了
  29.             path.pop_back();                    // 回溯
  30.         }
  31.     }
  33.     vector<string> letterCombinations(string digits){
  34.         result.clear();        // 可以不写
  35.         path.clear();        // 可以不写
  36.         if(digits.size() == 0) return result;
  37.         backTracking(digits, 0);
  38.         return result;
  39.     }
  40. };

6、回溯周末总结

还是看卡哥的吧，自己太懒了代码随想录 - 回溯算法 - 6. 回溯周末总结

7、组合总和

7.1、思路

重点需要注意的就是 startIndex 这个参数，因为题目说了，如果一个数字的被选数量不同，则是两种不同的组合，但是，[ 2, 3, 3 ] 和 [ 3, 2, 2 ]，被视为同一种组合，因此我们要求的不是排列，而是组合。
所以，当我们遍历了 i = 2 的所有情况之后，当 i = 3就不再对 数字小于3 的情况进行探究了，因为即使符合条件，也必定是和前面重复的。因此我们用一个 startIndex 参数来控制，巧妙的是，递归使用到了for循环中的参数 i。
image.png

C++完整代码如下：

  1. class Solution {
  2. private:
  3.     vector<vector<int>> result;     // 保存符合条件的结果集
  4.     vector<int> path;               // 保存遍历过程中符合条件的结果
  5.     int sum;                        // 记录path的各个元素的总和
  6.     void backTracking(vector<int>& candidates, int target, int startIndex){
  7.         if(sum > target){           // 如果sum大于target了，说明往后都不会满足条件，需要跳出当前递归
  8.             return;
  9.         }
  10.         if(sum == target){
  11.             result.push_back(path);
  12.             return;
  13.         }
  15.         for(int i = startIndex; i < candidates.size(); i++){
  16.             sum += candidates[i];
  17.             path.push_back(candidates[i]);
  18.             backTracking(candidates, target, i);
  19.             path.pop_back();
  20.             sum -= candidates[i];
  21.         }
  22.     }
  24. public:
  25.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  26.         result.clear();
  27.         path.clear();
  28.         backTracking(candidates, target, 0);
  29.         return result;
  30.     }
  31. };

7.2、剪枝优化

在这个树形结构中：
image.png
以及上面的版本一的代码大家可以看到，对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum > target的话就返回。
其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。

有个问题需要注意，就是以上的剪枝优化分析都是建立在 candinates 数组是一个有序的从小到大的数组进行的。

  1. class Solution {
  2. private:
  3.     vector<vector<int>> result;     // 保存符合条件的结果集
  4.     vector<int> path;               // 保存遍历过程中符合条件的结果
  5.     int sum = 0;                        // 记录path的各个元素的总和
  6.     void backTracking(vector<int>& candidates, int target, int startIndex){
  7.         // if(sum > target){           // 如果sum大于target了，说明往后都不会满足条件，需要跳出当前递归
  8.         //     return;
  9.         // }
  10.         if(sum == target){
  11.             result.push_back(path);
  12.             return;
  13.         }
  14.         // 如果 sum + canidates[i] > target 就终止后面的遍历
  15.         for(int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++){
  16.             sum += candidates[i];
  17.             path.push_back(candidates[i]);
  18.             backTracking(candidates, target, i);
  19.             sum -= candidates[i];
  20.             path.pop_back();
  21.         }
  22.     }
  24. public:
  25.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  26.         result.clear();
  27.         path.clear();
  28.         // 需要对数组进行排序
  29.         sort(candidates.begin(), candidates.end());
  30.         backTracking(candidates, target, 0);
  31.         return result;
  32.     }
  33. };

8、组合总和II

40. 组合总和 II - 力扣（LeetCode）

image.png
image.png

8.1、思路

如果对回溯算法基础还不了解的话，我还特意录制了一期视频：带你学透回溯算法（理论篇）(opens new window)可以结合题解和视频一起看，希望对大家理解回溯算法有所帮助。

这道题目和39.组合总和(opens new window)如下区别：

  1. 本题candidates 中的每个数字在每个组合中只能使用一次。
  2. 本题数组candidates的元素是有重复的，而39.组合总和(opens new window)是无重复元素的数组candidates

最后本题和39.组合总和(opens new window)要求一样，解集不能包含重复的组合。
本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。
一些同学可能想了：我把所有组合求出来，再用set或者map去重，这么做很容易超时！
所以要在搜索的过程中就去掉重复组合。

很多同学在去重的问题上想不明白，其实很多题解也没有讲清楚，反正代码是能过的，感觉是那么回事，稀里糊涂的先把题目过了。

这个去重为什么很难理解呢，所谓去重，其实就是使用过的元素不能重复选取。 这么一说好像很简单！
都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？
回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。
所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）
强调一下，树层去重的话，需要对数组排序！
选择过程树形结构如图所示：
image.png
可以看到图中，每个节点相对于 39.组合总和(opens new window)我多加了used数组，这个used数组下面会重点介绍。

  • 单层搜索的逻辑

这里与39.组合总和(opens new window)最大的不同就是要去重了。
前面我们提到：要去重的是“同一树层上的使用过”，如果判断同一树层上元素（相同的元素）是否使用过了呢。

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

此时for循环里就应该做continue的操作。
这块比较抽象，如图：
image.png

我在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

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

这块去重的逻辑很抽象，网上搜的题解基本没有能讲清楚的，如果大家之前思考过这个问题或者刷过这道题目，看到这里一定会感觉通透了很多！
那么单层搜索的逻辑代码如下：

  1. for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
  2.     // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
  3.     // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
  4.     // 要对同一树层使用过的元素进行跳过
  5.     if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
  6.         continue;
  7.     }
  8.     sum += candidates[i];
  9.     path.push_back(candidates[i]);
  10.     used[i] = true;
  11.     backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1：这里是i+1，每个数字在每个组合中只能使用一次
  12.     used[i] = false;
  13.     sum -= candidates[i];
  14.     path.pop_back();
  15. }

注意sum + candidates[i] <= target为剪枝操作，在39.组合总和(opens new window)有讲解过！
回溯三部曲分析完了，整体C++代码如下：

  1. class Solution {
  2. private:
  3.     vector<vector<int>> result;
  4.     vector<int> path;
  5.     void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
  6.         if (sum == target) {
  7.             result.push_back(path);
  8.             return;
  9.         }
  10.         for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
  11.             // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
  12.             // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
  13.             // 要对同一树层使用过的元素进行跳过
  14.             if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
  15.                 continue;
  16.             }
  17.             sum += candidates[i];
  18.             path.push_back(candidates[i]);
  19.             used[i] = true;
  20.             backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
  21.             used[i] = false;
  22.             sum -= candidates[i];
  23.             path.pop_back();
  24.         }
  25.     }
  27. public:
  28.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  29.         vector<bool> used(candidates.size(), false);
  30.         path.clear();
  31.         result.clear();
  32.         // 首先把给candidates排序，让其相同的元素都挨在一起。
  33.         sort(candidates.begin(), candidates.end());
  34.         backtracking(candidates, target, 0, 0, used);
  35.         return result;
  36.     }
  37. };

8.2、补充

这里直接用startIndex来去重也是可以的， 就不用used数组了。

  1. class Solution {
  2. private:
  3.     vector<vector<int>> result;
  4.     vector<int> path;
  5.     void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
  6.         if (sum == target) {
  7.             result.push_back(path);
  8.             return;
  9.         }
  10.         for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
  11.             // 要对同一树层使用过的元素进行跳过
  12.             if (i > startIndex && candidates[i] == candidates[i - 1]) {
  13.                 continue;
  14.             }
  15.             sum += candidates[i];
  16.             path.push_back(candidates[i]);
  17.             backtracking(candidates, target, sum, i + 1); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
  18.             sum -= candidates[i];
  19.             path.pop_back();
  20.         }
  21.     }
  23. public:
  24.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  25.         path.clear();
  26.         result.clear();
  27.         // 首先把给candidates排序，让其相同的元素都挨在一起。
  28.         sort(candidates.begin(), candidates.end());
  29.         backtracking(candidates, target, 0, 0);
  30.         return result;
  31.     }
  32. };

8.3、总结

本题同样是求组合总和，但就是因为其数组candidates有重复元素，而要求不能有重复的组合，所以相对于39.组合总和(opens new window)难度提升了不少。
关键是去重的逻辑，代码很简单，网上一搜一大把，但几乎没有能把这块代码含义讲明白的，基本都是给出代码，然后说这就是去重了，究竟怎么个去重法也是模棱两可。
所以Carl有必要把去重的这块彻彻底底的给大家讲清楚，就连“树层去重”和“树枝去重”都是我自创的词汇，希望对大家理解有帮助！

9、分割回文串

131. 分割回文串 - 力扣（LeetCode）

9.1、思路

关于本题，大家也可以看我在B站的视频讲解：131.分割回文串（B站视频）(opens new window)
本题这涉及到两个关键问题：

  1. 切割问题，有不同的切割方式
  2. 判断回文

相信这里不同的切割方式可以搞懵很多同学了。
这种题目，想用for循环暴力解法，可能都不那么容易写出来，所以要换一种暴力的方式，就是回溯。
一些同学可能想不清楚 回溯究竟是如何切割字符串呢？
我们来分析一下切割，其实切割问题类似组合问题。
例如对于字符串abcdef：

  • 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…..。
  • 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…..。

感受出来了不？
所以切割问题，也可以抽象为一棵树形结构，如图：
image.png

递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。
此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

  • 要明确递归的终止条件：切割线切割到了字符串的最后面，说明找到了一种切割方法，此时就是本层递归的终止条件。

那么在代码里什么是分割线呢？
在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是字符串的分割线。
所以终止条件代码如下：

  1. void backtracking (const string& s, int startIndex) {
  2.     // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
  3.     if (startIndex >= s.size()) {
  4.         result.push_back(path);
  5.         return;
  6.     }
  7. }
  • 单层搜索的逻辑

来看看在递归循环中，如何截取子串？
在for (int i = startIndex; i < s.size(); i++)循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文，如果是回文，就加入在vector path中，path用来记录切割过的回文子串。
代码如下：

  1. for (int i = startIndex; i < s.size(); i++) {
  2.     if (isPalindrome(s, startIndex, i)) { // 是回文子串
  3.         // 获取[startIndex,i]在s中的子串
  4.         string str = s.substr(startIndex, i - startIndex + 1);
  5.         path.push_back(str);
  6.     } else {                // 如果不是则直接跳过
  7.         continue;
  8.     }
  9.     backtracking(s, i + 1); // 寻找i+1为起始位置的子串
  10.     path.pop_back();        // 回溯过程，弹出本次已经填在的子串
  11. }

注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1。

C++完整代码如下：

  1. class Solution {
  2. private:
  3.     vector<vector<string>> result;
  4.     vector<string> path;    // 存放已经回文的子串
  6.     // 判断是否回文串
  7.     bool palindrome(const string& s, int start, int end){
  8.         for(int i = start, j = end; i < j; i++, j--){
  9.             if(s[i] != s[j]){
  10.                 return false;
  11.             }
  12.         }
  13.         return true;
  14.     }
  16.     // 回溯模拟分割回文串
  17.     void backTracking(const string& s, int startIndex){
  18.         // 如果startIndex大于等于字符串s的大小，说明已经找到一组分割方案了
  19.         if(startIndex >= s.size()){
  20.             result.push_back(path);
  21.             return;
  22.         }
  24.         for(int i = startIndex; i < s.size(); i++){
  25.             // 如果当前分割的子串是一个回文串，那么把它压入result
  26.             if(palindrome(s, startIndex, i) == true){
  27.                 // 获取 [startIndex, i] 在s中的子串
  28.                 string subString = s.substr(startIndex, i - startIndex + 1);
  29.                 path.push_back(subString);
  30.             }
  31.             else{
  32.                 continue;       // 不是回文串，跳过
  33.             }
  34.             backTracking(s, i + 1);     // 寻早i+1为起点的回文子串
  35.             path.pop_back();            // 回溯，弹出已经填充进去的回文子串
  36.         }
  37.     }
  39. public:
  40.     vector<vector<string>> partition(string s) {
  41.         result.clear();     // 可以不写
  42.         path.clear();
  43.         backTracking(s, 0);
  44.         return result;
  45.     }
  46. };

9.2、总结

写完题目后也需要反复思考的几个问题

  1. 切割问题可以抽象为组合问题
  2. 如何模拟切割线
  3. 切割问题中递归如何终止
  4. 在递归循环中如何截取子串
  5. 如何判断回文

10、复原IP地址

93. 复原IP地址 - 力扣（LeetCode）

思路：

  1. 需要一个pointNum来记录插入逗点的数量
  2. 当pointNum == 3时，说明已经将字符串分成4段，但此时需要验证第4段的字符串是否合法
  3. 编写一个验证字符串是否合法的函数。

  4. 不能重复分割，因此startIndex是需要的。 ```cpp class Solution { private: vector result; // 保存符合条件的结果集 void backTracking(string s, int startIndex, int pointNum){ // pointNum表示IP地址的分割点 ‘.’

    1.  if(pointNum == 3){      // 如果pointNum == 3，说明已经将字符串分成4段
    2.      // 判断第4段是否合法，如果合法就放入结果数组
    3.      if(isValid(s, startIndex, s.size() - 1)){
    4.          result.push_back(s);
    5.      }
    6.      return;
    7.  }
    9.  for(int i = startIndex; i < s.size(); i++){
    10.      if(isValid(s, startIndex, i) == true){  // 判断 [startIndex, i]这个区间的字符串是否合法
    11.          s.insert(s.begin() + i + 1, '.');   // 在i的后面插入一个逗点.
    12.          pointNum++;                         // 记录逗点的数量加1
    13.          backTracking(s, i + 2, pointNum);   // 因为插入了逗点，所以这里不是i+1，而是i+2
    14.          pointNum--;                         // 回溯
    15.          s.erase(s.begin() + i + 1);         // 回溯，将插入的逗点丢弃
    16.      }
    17.      else{
    18.          break;  // 如果字符串不合法，直接退出循环
    19.      }
    20.  }

    }

    // 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法 bool isValid(const string& s, int start, int end){

    1.  if(start > end){
    2.      return false;
    3.  }
    4.  if(s[start] == '0' && start != end){    // 如果前导是0，不合法
    5.      return false;
    6.  }
    7.  int sum = 0;
    8.  for(int i = start; i <= end; i++){
    9.      if(s[i] < '0' || s[i] > '9'){       // 遇到非法数字不合法
    10.          return false;
    11.      }
    12.      sum = sum * 10 + (s[i] - '0');
    13.      if(sum < 0 || sum > 255){       // 如果小于0或者大于255，则不合法
    14.          return false;
    15.      }
    16.  }
    17.  return true;

    }

public: vector restoreIpAddresses(string s) { result.clear(); // 可以不写，但是写上程序更加安全 if(s.size() > 12){ // 算是一个简单的剪枝 return result; } backTracking(s, 0, 0); return result; } };

  3. <a name="bJNms"></a>
  4. # 11、子集问题
  5. [78. 子集 - 力扣（LeetCode）](https://leetcode-cn.com/problems/subsets/)
  7. ![image.png](https://cdn.nlark.com/yuque/0/2022/png/21723656/1645512725372-46bdb0b0-f4a8-4d8e-b9df-f3ef0e212c03.png#clientId=ucbd310fa-8398-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=603&id=u3ca2c8d2&margin=%5Bobject%20Object%5D&name=image.png&originHeight=603&originWidth=616&originalType=binary&ratio=1&rotation=0&showTitle=false&size=30653&status=done&style=none&taskId=u39c3bc42-f8ae-4133-b5f1-ef0cd469b89&title=&width=616)
  9. 思路<br />求子集问题和 前面的 [77.组合(opens new window)](https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html)和[131.分割回文串(opens new window)](https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html)又不一样了。<br />如果把子集问题、组合问题、分割问题都抽象为一棵树的话，**那么组合问题和分割问题都是收集树的叶子结点，而子集问题是找树的所有节点！**
  11. 其实子集也是一种组合问题，因为它的集合是无序的，子集 {1, 2} 和子集 {2, 1} 是一样的。<br />**那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！**
  13. 那么什么时候for可以从0开始呢？<br />求排列问题的时候，就要从0开始，因为集合是有序的，{1, 2} 和{2, 1}是两个集合，排列问题我们后续的文章就会讲到的。<br />以示例中nums = [1,2,3]为例把求子集抽象为树型结构，如下：<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/21723656/1645513021930-bc032f74-8976-45da-88f0-8df605984df3.png#clientId=ucbd310fa-8398-4&crop=0&crop=0&crop=1&crop=1&from=paste&id=ufed47307&margin=%5Bobject%20Object%5D&name=image.png&originHeight=902&originWidth=1546&originalType=url&ratio=1&rotation=0&showTitle=false&size=182235&status=done&style=none&taskId=uc4989d1b-6d9c-4344-ba14-9cfb676110b&title=)<br />从图中红线部分，可以看出**遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合**。
  15. <a name="fSpfm"></a>
  16. ## 11.1、回溯三部曲
  18. - 递归函数参数
  20. 全局变量数组path为子集收集元素，二维数组result存放子集组合。（也可以放到递归函数参数里）<br />递归函数参数在上面讲到了，需要startIndex。<br />代码如下：
  21. ```cpp
  22. vector<vector<int>> result;
  23. vector<int> path;
  24. void backtracking(vector<int>& nums, int startIndex) {

递归终止条件
从图中可以看出：
image.png

剩余集合为空的时候，就是叶子节点。
那么什么时候剩余集合为空呢？
就是startIndex已经大于数组的长度了，就终止了，因为没有元素可取了，代码如下:

  1. if (startIndex >= nums.size()) {
  2.     return;
  3. }

其实可以不需要加终止条件，因为startIndex >= nums.size()，本层for循环本来也结束了。

  • 单层搜索逻辑

求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。
那么单层递归逻辑代码如下：

  1. for (int i = startIndex; i < nums.size(); i++) {
  2.     path.push_back(nums[i]);    // 子集收集元素
  3.     backtracking(nums, i + 1);  // 注意从i+1开始，元素不重复取
  4.     path.pop_back();            // 回溯
  5. }

C++代码

  1. class Solution {
  2. private:
  3.     vector<vector<int>> result;
  4.     vector<int> path;
  5.     void backtracking(vector<int>& nums, int startIndex) {
  6.         result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
  7.         if (startIndex >= nums.size()) { // 终止条件可以不加
  8.             return;
  9.         }
  10.         for (int i = startIndex; i < nums.size(); i++) {
  11.             path.push_back(nums[i]);
  12.             backtracking(nums, i + 1);
  13.             path.pop_back();
  14.         }
  15.     }
  16. public:
  17.     vector<vector<int>> subsets(vector<int>& nums) {
  18.         result.clear();
  19.         path.clear();
  20.         backtracking(nums, 0);
  21.         return result;
  22.     }
  23. };

在注释中，可以发现可以不写终止条件，因为本来我们就要遍历整棵树。
有的同学可能担心不写终止条件会不会无限递归？
并不会，因为每次递归的下一层就是从i+1开始的。

11.2、总结

相信大家经过了

洗礼之后，发现子集问题还真的有点简单了，其实这就是一道标准的模板题。
但是要清楚子集问题和组合问题、分割问题的的区别，子集是收集树形结构中树的所有节点的结果。
而组合问题、分割问题是收集树形结构中叶子节点的结果。

12、回溯周末总结

本周小结！（回溯算法系列二）

例行每周小结

周一

在回溯算法：求组合总和（二）(opens new window)中讲解的组合总和问题，和以前的组合问题还都不一样。
本题和回溯算法：求组合问题！(opens new window)，回溯算法：求组合总和！(opens new window)和区别是：本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。
不少录友都是看到可以重复选择，就义无反顾的把startIndex去掉了。
本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？
我举过例子，如果是一个集合来求组合的话，就需要startIndex，例如：回溯算法：求组合问题！(opens new window)，回溯算法：求组合总和！(opens new window)。
如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：回溯算法：电话号码的字母组合(opens new window)
注意以上我只是说求组合的情况，如果是排列问题，又是另一套分析的套路，后面我再讲解排列的时候就重点介绍。
最后还给出了本题的剪枝优化，如下：

  1. for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++)

这个优化如果是初学者的话并不容易想到。
在求和问题中，排序之后加剪枝是常见的套路！
在回溯算法：求组合总和（二）(opens new window)第一个树形结构没有画出startIndex的作用，这里这里纠正一下，准确的树形结构如图所示：
image.png

周二

在回溯算法：求组合总和（三）(opens new window)中依旧讲解组合总和问题，本题集合元素会有重复，但要求解集不能包含重复的组合。
所以难就难在去重问题上了。
这个去重问题，相信做过的录友都知道有多么的晦涩难懂。网上的题解一般就说“去掉重复”，但说不清怎么个去重，代码一甩就完事了。
为了讲解这个去重问题，我自创了两个词汇，“树枝去重”和“树层去重”。
都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上“使用过”，一个维度是同一树层上“使用过”。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。
image.png
我在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

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

这块去重的逻辑很抽象，网上搜的题解基本没有能讲清楚的，如果大家之前思考过这个问题或者刷过这道题目，看到这里一定会感觉通透了很多！
对于去重，其实排列问题也是一样的道理，后面我会讲到。

周三

在回溯算法：分割回文串(opens new window)中，我们开始讲解切割问题，虽然最后代码看起来好像是一道模板题，但是从分析到学会套用这个模板，是比较难的。
我列出如下几个难点：

  • 切割问题其实类似组合问题
  • 如何模拟那些切割线
  • 切割问题中递归如何终止
  • 在递归循环中如何截取子串
  • 如何判断回文

如果想到了用求解组合问题的思路来解决 切割问题本题就成功一大半了，接下来就可以对着模板照葫芦画瓢。
但后序如何模拟切割线，如何终止，如何截取子串，其实都不好想，最后判断回文算是最简单的了。
除了这些难点，本题还有细节，例如：切割过的地方不能重复切割所以递归函数需要传入i + 1。
所以本题应该是一个道hard题目了。
本题的树形结构中，和代码的逻辑有一个小出入，已经判断不是回文的子串就不会进入递归了，纠正如下：
image.png

周四

如果没有做过回溯算法：分割回文串(opens new window)的话，回溯算法：复原IP地址(opens new window)这道题目应该是比较难的。
复原IP照回溯算法：分割回文串(opens new window)就多了一些限制，例如只能分四段，而且还是更改字符串，插入逗点。
树形图如下：
image.png
在本文的树形结构图中，我已经把详细的分析思路都画了出来，相信大家看了之后一定会思路清晰不少！
本题还可以有一个剪枝，合法ip长度为12，如果s的长度超过了12就不是有效IP地址，直接返回！
代码如下：

  1. if (s.size() > 12) return result; // 剪枝

我之前给出的C++代码没有加这个限制，也没有超时，因为在第四段超过长度之后，就会截止了，所以就算给出特别长的字符串，搜索的范围也是有限的（递归只会到第三层），及时就会返回了。

周五

在回溯算法：求子集问题！(opens new window)中讲解了子集问题，在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果。
如图：
image.png
认清这个本质之后，今天的题目就是一道模板题了。
其实可以不需要加终止条件，因为startIndex >= nums.size()，本层for循环本来也结束了，本来我们就要遍历整棵树。
有的同学可能担心不写终止条件会不会无限递归？
并不会，因为每次递归的下一层就是从i+1开始的。
如果要写终止条件，注意：result.push_back(path);要放在终止条件的上面，如下：

  1. result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
  2. if (startIndex >= nums.size()) { // 终止条件可以不加
  3.     return;
  4. }

周六

早起的哈希表系列没有总结，所以哈希表：总结篇！（每逢总结必经典）(opens new window)如约而至。
可能之前大家做过很多哈希表的题目，但是没有串成线，总结篇来帮你串成线，捋顺哈希表的整个脉络。
大家对什么时候各种set与map比较疑惑，想深入了解红黑树，哈希之类的。
如果真的只是想清楚什么时候使用各种set与map，不用看那么多，把关于哈希表，你该了解这些！(opens new window)看了就够了。

13、子集问题II

90. 子集 II - 力扣（LeetCode）

13.1、思路

做本题之前一定要先做78.子集(opens new window)。
这道题目和78.子集(opens new window)区别就是集合里有重复元素了，而且求取的子集要去重。

关于回溯算法中去重的问题，在40.组合总和II中已经详细分析了，跟本题是一模一样的套路。
剧透一下，后期要讲的排列问题里去重也是这个套路，所以理解 “树枝去重” 和 “树层去重” 十分重要！！！

用示例中的[1, 2, 2] 来举例，如图所示： （注意去重需要先对集合排序）
image.png
从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！

C++代码如下：

  1. class Solution {
  2. private:
  3.     vector<vector<int>> result;
  4.     vector<int> path;
  5.     void backTracking(vector<int>& nums, int startIndex, vector<bool> used){
  6.         result.push_back(path);
  7.         if(startIndex >= nums.size()){  // 这里其实可以省略，因为当startIndex > nums.size()回自动退出递归
  8.             return;
  9.         }
  10.         for(int i = startIndex; i < nums.size(); i++){
  11.             // 当used[i - 1] == true, 表示同一树枝nums[i - 1]使用过
  12.             // 当used[i - 1] == false, 表示同一树层nums[i - 1]使用过
  13.             if(i >= 1 && nums[i - 1] == nums[i] && used[i - 1] == false){
  14.                 continue;
  15.             }
  16.             path.push_back(nums[i]);
  17.             used[i] = true;
  18.             backTracking(nums, i + 1, used);
  19.             used[i] = false;
  20.             path.pop_back();
  21.         }
  22.     }
  24. public:
  25.     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  26.         result.clear();
  27.         path.clear();
  28.         sort(nums.begin(), nums.end());         // 对nums数组进行排序，使得他们重复的元素靠在一起
  29.         vector<bool> used(nums.size(), false);  // 初始化user
  30.         backTracking(nums, 0, used);
  31.         return result;
  32.     }
  33. };

13.2、补充

本题也可以不使用used数组来去重，因为递归的时候下一个startIndex是 i + 1 而不是 0。
如果要是全排列的化，每次要从0开始遍历，为了跳过已入栈的元素，需要适用used。

用startIndex去重后的代码如下：

  1. class Solution {
  2. private:
  3.     vector<vector<int>> result;
  4.     vector<int> path;
  5.     void backtracking(vector<int>& nums, int startIndex) {
  6.         result.push_back(path);
  7.         for (int i = startIndex; i < nums.size(); i++) {
  8.             // 而我们要对同一树层使用过的元素进行跳过
  9.             if (i > startIndex && nums[i] == nums[i - 1] ) { // 注意这里使用i > startIndex
  10.                 continue;
  11.             }
  12.             path.push_back(nums[i]);
  13.             backtracking(nums, i + 1);
  14.             path.pop_back();
  15.         }
  16.     }
  18. public:
  19.     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  20.         result.clear();
  21.         path.clear();
  22.         sort(nums.begin(), nums.end()); // 去重需要排序
  23.         backtracking(nums, 0);
  24.         return result;
  25.     }
  26. };

14、递增子序列

491. 递增子序列 - 力扣（LeetCode）
image.png
思路

  1. 不能重复取，与组合问题无异！所以用 startIndex
  2. 如果path是一个有序且升序的数组，且path的大小应该至少为2，这样才合法
  3. 当startIndex大于nums.size()，说明当前树枝已经遍历完了（这个判断其实可以不写）
  4. 树层去重，可以使用 vector used 或者利用 startIndex
  5. 因为给定的树枝nums可能有重复元素，且有可能不相邻，所以需要用哈希集合/映射 来保存，这里用哈希集合就够了。
  6. 可以用数组来替代哈希集合，起到优化作用

C++代码（优化前）

  1. class Solution {
  2. private:
  3.     vector<vector<int>> result;
  4.     vector<int> path;
  5.     void backTracking(vector<int>& nums, int startIndex){
  6.         // 1.如果path是一个有序且升序的数组，且path的大小应该至少为2，这样则合法
  7.         if(is_sorted(path.begin(), path.end()) && path.size() >= 2){
  8.             result.push_back(path);
  9.         }
  10.         // 2.当startIndex大于nums.size()，说明当前树枝已经遍历完了(这个判断其实可以不写，for循环自己会判断)
  11.         if(startIndex > nums.size()){
  12.             return;
  13.         }
  14.         unordered_set<int> set;
  15.         for(int i = startIndex; i < nums.size(); i++){
  16.             // 利用startIndex实现树层去重(为什么是树层？因为 i > startIndex 的时候，表明这个当前这个节点的树枝遍历完毕，要开始遍历树层了)
  17.             if(i > startIndex && set.find(nums[i]) != set.end()){
  18.                 continue;
  19.             }
  20.             set.insert(nums[i]);
  21.             path.push_back(nums[i]);
  22.             backTracking(nums, i + 1);
  23.             path.pop_back();
  24.         }
  25.     }
  27. public:
  28.     vector<vector<int>> findSubsequences(vector<int>& nums) {
  29.         result.clear();
  30.         path.clear();
  31.         backTracking(nums, 0);
  32.         return result;
  33.     }
  34. };

C++代码（优化后）

  1. class Solution {
  2. private:
  3.     vector<vector<int>> result;
  4.     vector<int> path;
  5.     void backTracking(vector<int>& nums, int startIndex){
  6.         // 1.如果path是一个有序且升序的数组，且path的大小应该至少为2，这样则合法
  7.         if(is_sorted(path.begin(), path.end()) && path.size() >= 2){
  8.             result.push_back(path);
  9.         }
  10.         // 2.当startIndex大于nums.size()，说明当前树枝已经遍历完了(这个判断其实可以不写，for循环自己会判断)
  11.         if(startIndex > nums.size()){
  12.             return;
  13.         }
  14.         int used[201] = {0}; // 这里使用数组来进行去重操作，题目说数值范围[-100, 100]
  15.         for(int i = startIndex; i < nums.size(); i++){
  16.             // 利用startIndex实现树层去重(为什么是树层？因为 i > startIndex 的时候，表明这个当前这个节点的树枝遍历完毕，要开始遍历树层了)
  17.             if(i > startIndex && used[nums[i] + 100] == 1){
  18.                 continue;
  19.             }
  20.             used[nums[i] + 100] = 1; // 记录这个元素在本层用过了，本层后面不能再用了
  21.             path.push_back(nums[i]);
  22.             backTracking(nums, i + 1);
  23.             path.pop_back();
  24.         }
  25.     }
  27. public:
  28.     vector<vector<int>> findSubsequences(vector<int>& nums) {
  29.         result.clear();
  30.         path.clear();
  31.         backTracking(nums, 0);
  32.         return result;
  33.     }
  34. };

15、全排列

46. 全排列 - 力扣（LeetCode）

image.png

  1. 递归函数参数与返回值
  • 首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。
  • 可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。
    1. vector<vector<int>> result;
    2. vector<int> path;
    3. void backtracking (vector<int>& nums, vector<bool>& used)
  1. 递归终止条件

image.png
叶子节点，就是收割结果的地方。那么什么时候是叶子节点呢？
当收集元素的数组path的大小和nums数组的大小一样大的时候，说明找到了一个全排列，也表示到达了叶子节点

  1. // 此时说明找到了一组
  2. if (path.size() == nums.size()) {
  3.     result.push_back(path);
  4.     return;
  5. }
  1. 单层搜索的逻辑

使用 vector<bool>used来记录path里有哪些元素已经被使用过了。

  1. // used[i] == true，表示数组中第i个元素已经使用过了，下次不能再使用
  2. for(int i = 0; i < nums.size(); i++){
  3.     if(used[i] == true){
  4.         continue;
  5.     }
  6.     used[i] = true;
  7.     path.push_back(nums[i]);
  8.     backTracking(nums, used);
  9.     used[i] = false;
  10.     path.pop_back();
  11. }

C++完整代码如下：

  1. class Solution {
  2. private:
  3.     vector<vector<int>> result;
  4.     vector<int> path;
  5.     void backTracking(vector<int>& nums, vector<bool> used){
  6.         if(path.size() == nums.size()){
  7.             result.push_back(path);
  8.             return;
  9.         }
  10.         // used[i] == true，表示数组中第i个元素已经使用过了，下次不能再使用
  11.         for(int i = 0; i < nums.size(); i++){
  12.             if(used[i] == true){
  13.                 continue;
  14.             }
  15.             used[i] = true;
  16.             path.push_back(nums[i]);
  17.             backTracking(nums, used);
  18.             used[i] = false;
  19.             path.pop_back();
  20.         }
  21.     }
  23. public:
  24.     vector<vector<int>> permute(vector<int>& nums) {
  25.         result.clear();
  26.         path.clear();
  27.         vector<bool> used(nums.size(), false);
  28.         backTracking(nums, used);
  29.         return result;
  30.     }
  31. };

16、全排列 II

47. 全排列 II - 力扣（LeetCode）

image.png

这道题目和46.全排列(opens new window)的区别在于给定了一个可包含重复数字的序列，要返回所有不重复的全排列。
这就又涉及到去重的概念了。
去重

  • 树枝去重
  • 树层去重

这里这两个都用到了，树枝去重是去掉上次在path中被使用了的哪些元素，树层去重是去掉序列中的重复数字。
需要强调一点的是，树层去重一定要对数组进行排序，我们才方便通过相邻的节点来判断是否重复使用了

C++完整代码：

  1. class Solution {
  2. private:
  3.     vector<vector<int>> result;
  4.     vector<int> path;
  5.     void backTracking(vector<int>& nums, vector<bool>& used){
  6.         if(nums.size() == path.size()){
  7.             result.push_back(path);
  8.             return;
  9.         }
  10.         // 记录path里有哪些元素已经被使用过了：used[i] == true
  11.         // 树层去重：i >= 1 && nums[i - 1] == nums[i] && used[i - 1] == false
  12.         for(int i = 0; i < nums.size(); i++){
  13.             // 注意if语句的判断从左到右
  14.             if(used[i] == true || (i >= 1 && nums[i - 1] == nums[i] && used[i - 1] == false)){
  15.                 continue;
  16.             }
  17.             used[i] = true;
  18.             path.push_back(nums[i]);
  19.             backTracking(nums, used);
  20.             used[i] = false;
  21.             path.pop_back();
  22.         }
  23.     }
  25. public:
  26.     vector<vector<int>> permuteUnique(vector<int>& nums) {
  27.         result.clear();
  28.         path.clear();
  29.         sort(nums.begin(), nums.end());     // 对nums数组进行排序，让重复的元素挨在一起
  30.         vector<bool> used(nums.size(), false);
  31.         backTracking(nums, used);
  32.         return result;
  33.     }
  34. };

拓展

image.png
在这里我用的是树层去重，但其实，树枝去重也是可以的，只不过树层去重的效率更高。关于树枝去重和树层去重，卡哥在回溯算法 - 16.全排列II - 拓展里面说的挺详细的。如果忘记了回去看看。下面我只贴上两张图来区分它们的不同。

树层上去重(used[i - 1] == false)，的树形结构如下：
image.png

树枝上去重（used[i - 1] == true）的树型结构如下：
image.png

17、回溯周末总结

对

  1. 子集问题2
  2. 递增子序列
  3. 全排列
  4. 全排列2

进行了总结

具体看卡哥的代码随想录：周总结/20201112回溯周末总结.html#周一

性能分析

之前并没有分析各个问题的时间复杂度和空间复杂度，这次来说一说。
这块网上的资料鱼龙混杂，一些所谓的经典面试书籍根本不讲回溯算法，算法书籍对这块也避而不谈，感觉就像是算法里模糊的边界。
所以这块就说一说我个人理解，对内容持开放态度，集思广益，欢迎大家来讨论！

子集问题分析：

  • 时间复杂度：$O(n × 2^n)$，因为每一个元素的状态无外乎取与不取，所以时间复杂度为$O(2^n)$，构造每一组子集都需要填进数组，又有需要$O(n)$，最终时间复杂度：$O(n × 2^n)$。
  • 空间复杂度：$O(n)$，递归深度为n，所以系统栈所用空间为$O(n)$，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为$O(n)$。

排列问题分析：

  • 时间复杂度：$O(n!)$，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n n-1 n-2 * ….. 1 = n!。
  • 空间复杂度：$O(n)$，和子集问题同理。

组合问题分析：

  • 时间复杂度：$O(n × 2^n)$，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。
  • 空间复杂度：$O(n)$，和子集问题同理。

一般说道回溯算法的复杂度，都说是指数级别的时间复杂度，这也算是一个概括吧！

18、回溯算法去重问题的另一种写法

卡哥对一些录友在去重问题上犯的错误进行的分析和更改，主要是题目

也是我很容易犯的错误，值得一看！
代码随想录 - 回溯算法 - 18. 回溯算法去重问题的另一种写法

19、重新安排行程（困难）

332. 重新安排行程 - 力扣（LeetCode）

image.png
image.png

思路：
这道题目有几个难点：

  1. 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
  2. 有多种解法，字母序靠前排在前面，如何记录映射关系呢？
  3. 使用回溯法（也可以说深度优先搜索）的话，终止条件是什么？
  4. 搜索的过程中，如何遍历一个机场所对应的所有机场？

问题1：给每一个航班一个记录，即一个目的机场只能飞一次，使用 unordered_map<出发机场, map<目的机场, 航班次数>> targets来解决。
问题2：map的key是有序的，所以在初始化 targets 的时候，已经完成了字母的排序问题。
问题3：tickets.size( ) + 1 == result.size( )；说明找到了一条最佳航线
问题4：当航班次数 > 0，遍历就不会停止，知道航班次数全部为0.

C++完整代码

  1. class Solution {
  2. private:
  3.     // unordered_map<出发机场, map<目的机场, 航班次数>> targets
  4.     unordered_map<string, map<string, int>> targets;        // map是的key是有序的
  5.     bool backTracking(int ticketNum, vector<string>& result){
  6.         if(result.size() == ticketNum + 1){
  7.             return true;
  8.         }
  9.         for(pair<const string, int>& target : targets[result[result.size() - 1]]){
  10.             if(target.second > 0){                // 记录到达机场是否飞过了
  11.                 result.push_back(target.first);
  12.                 target.second--;
  13.                 if(backTracking(ticketNum, result) == true) return true;
  14.                 result.pop_back();
  15.                 target.second++;
  16.             }
  17.         }
  18.         return false;
  19.     }
  21. public:
  22.     vector<string> findItinerary(vector<vector<string>>& tickets) {
  23.         targets.clear();
  24.         vector<string> result;
  25.         result.push_back("JFK");            // 起始航班是 "JFK"
  26.         for(const vector<string> vec : tickets){
  27.             targets[vec[0]][vec[1]]++;      // 记录映射关系
  28.         }
  29.         backTracking(tickets.size(), result);
  30.         return result;
  31.     }
  32. };

需要注意的是 unordered_map<string, map<string, int>> targets; unordered_map里面嵌套了map，而map的key是有序的，所以就解决了：如果存在多种有效的行程，按字典排序返回最小的行程组合 这一问题了。
且这道题目最难的地方是容器的选择和使用上，这一点是很难想到的，如果能想到这一点，这道题就算解决了一大半了。

如果还是搞不懂，看代码随想录：回溯算法 - 19. 重新安排行程

20、N皇后（困难）

51. N皇后 - 力扣（LeetCode）
image.png
image.png
思路
皇后们的约束条件：

  1. 不能同行
  2. 不能同列
  3. 不能同斜线

确定完约束条件，需要判断如何去搜索皇后们的位置，其实搜索皇后的位置可以抽象为一棵树。
下面我用一个 3 * 3 的棋盘，将搜索过程抽象为一棵树，如图：
image.png

从图中，可以看出，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。
那么我们用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。

C++完整代码

  1. class Solution{
  2. private:
  3.     vector<vector<string>> result;
  4.     void backTracking(int row, vector<string>& chessboard, int n) {
  5.         if(row == n){
  6.             result.push_back(chessboard);
  7.             return;
  8.         }
  9.         for(int col = 0; col < n; col++){
  10.             if(isValid(row, col, chessboard, n) == true){
  11.                 chessboard[row][col] = 'Q';
  12.                 backTracking(row + 1, chessboard, n);
  13.                 chessboard[row][col] = '.';            // 回溯
  14.             }
  15.         }
  16.     }
  18.     // 验证棋盘是否合法
  19.     bool isValid(int row, int col, vector<string>& chessboard, int n){
  20.         // 验证列是否有皇后
  21.         for(int i = 0; i < row; i++){
  22.             if(chessboard[i][col] == 'Q'){
  23.                 return false;
  24.             }
  25.         }
  26.         // 验证45°是否有皇后
  27.         for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
  28.             if(chessboard[i][j] == 'Q'){
  29.                 return false;
  30.             }
  31.         }
  32.         // 验证135°是否有皇后
  33.         for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){
  34.             if(chessboard[i][j] == 'Q'){
  35.                 return false;
  36.             }
  37.         }
  38.         return true;
  39.     }
  41. public:
  42.     vector<vector<string>> solveNQueens(int n) {
  43.         result.clear();
  44.         vector<string> chessboard(n, string(n, '.'));
  45.         backTracking(0, chessboard, n);
  46.         return result;
  47.     }
  48. };

21、解数独（困难）

37. 解数独 - 力扣（LeetCode）

image.png
image.png
image.png

思路：
N皇后问题(opens new window)是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来来遍历列，然后一行一列确定皇后的唯一位置。
本题就不一样了，本题中棋盘的每一个位置都要放一个数字，并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。

因为这个树形结构太大了，我抽取一部分，如图所示：
image.png

思考：

  1. 二维递归
  2. 递归函数的返回值为什么是bool型？
  3. 不用终止条件会不会死循环？
  4. 有没有永远填不满的情况？
  5. 判断棋盘是否合法
    1. 同行是否重复
    2. 同列是否重复
    3. 9宫格里是否重复

如果想不出来这些思考点，看卡哥的解释：代码随想录 - 回溯算法 - 21. 解数独

C++完整代码：

  1. class Solution {
  2. private:
  3.     bool backTracking(vector<vector<char>>& board){
  4.         for(int row = 0; row < board.size(); row++){        // 遍历行
  5.             for(int col = 0; col < board[0].size(); col++){ // 遍历列
  6.                 if(board[row][col] != '.'){
  7.                     continue;                               // 遇到非'.'要跳过，不然col=0，出不来，陷入死循环
  8.                 }
  9.                 // cout << "board[" << row << "][" << col << "]" << board[row][col] << endl;
  10.                 for(char val = '1'; val <= '9'; val++){
  11.                     if(isValid(row, col, val, board)){      // 判断val放在board[row][val]这个位置是否合法
  12.                         board[row][col] = val;              // 放置val
  13.                         if(backTracking(board)){
  14.                             return true;                    // 如果找到合适的数独解，马上返回
  15.                         }
  16.                         board[row][col] = '.';              // 回溯，撤销val
  17.                     }
  18.                 }
  19.                 return false;                               // 如果一行一列确定下来，某个位置尝试了9个数字都不行，说明数独的解法不存在
  20.             }
  21.         }
  22.         return true;                                        // 遍历完没有返回false，说明找到了合适棋盘位置了
  23.     }
  24.     // 判断填入的数字是否合法
  25.     bool isValid(int row, int col, char val, vector<vector<char>>& board){
  26.             // 检验行里的数字是否重复
  27.             for(int i = 0; i < 9; i++){
  28.                 if(board[row][i] == val){
  29.                     return false;
  30.                 }
  31.             }
  32.             // 检验列里的数字是否重复
  33.             for(int i = 0; i < 9; i++){
  34.                 if(board[i][col] == val){
  35.                     return false;
  36.                 }
  37.             }
  38.             // 判断9方格里是否重复
  39.             int startRow = (row / 3) * 3;
  40.             int startCol = (col / 3) * 3;
  41.             for(int i = startRow; i < startRow + 3; i++){
  42.                 for(int j = startCol; j < startCol + 3; j++){
  43.                     if(board[i][j] == val){
  44.                         return false;
  45.                     }
  46.                 }
  47.             }
  48.             return true;
  49.         }
  50. public:
  51.     void solveSudoku(vector<vector<char>>& board) {
  52.         if(backTracking(board)){
  53.             cout << "数独有解！";
  54.         }
  55.         else{
  56.             cout << "数独无解！";
  57.         }
  58.     }
  59. };

22、回溯法总结篇

千好万好还是卡哥总结的好！代码随想录 - 回溯算法 - 22. 回溯法总结篇

image.png