回溯总结篇

待我称王封你为后i 2023-10-16 14:11 15阅读 0赞

#### 回溯总结篇 ####

*  回溯法理论基础
 *  组合问题
 *  组合总和
 *   *  组合总和（一）
     *  组合总和（二）
     *  组合总和（三）
 *  多个集合求组合
 *  切割问题
 *  子集问题
 *   *  子集问题（一）
     *  子集问题（二）
 *  递增子序列
 *  排列问题
 *   *  排列问题（一）
     *  排列问题（二）
 *  去重问题
 *  重新安排行程（图论额外拓展）
 *  棋盘问题
 *   *  N皇后问题
     *  解数独问题
 *  性能分析
 *   *  子集问题分析
     *  排列问题分析
     *  组合问题分析
     *  N皇后问题分析
     *  解数独问题分析
 *  总结

## 回溯法理论基础 ##

**回溯是递归的副产品，只要有递归就会有回溯**，所以回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。

回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。

回溯算法能解决如下问题：

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

回溯法确实不好理解，所以需要把回溯法抽象为一个图形来理解就容易多了，在后面的每一道回溯法的题目我都将遍历过程抽象为**树形结构**方便大家的理解。

在关于**回溯算法，你该了解这些**还用了回溯三部曲来分析回溯算法，并给出了回溯法的模板：

void backtracking(参数){
        
    	if(终止条件){
        
    		存放结果;
    		return;
    	}
    
    	for(选择: 本层集合中元素(树中节点孩子的数量就是集合的大小)){
        
    		处理节点;
    		backtracking(路径，选择列表); // 递归
    		回溯, 撤销处理结果
    	}
    }

**事实证明这个模板会伴随整个回溯法系列！**

## 组合问题 ##

在**回溯算法：求组合问题**中，我们开始用回溯法解决第一道题目：组合问题。

我在文中开始的时候给大家列举k层for循环例子，进而得出都是同样是暴力解法，为什么要用回溯法！

**此时大家应该深有体会回溯法的魅力，用递归控制for循环嵌套的数量！**

本题我把回溯问题抽象为树形结构，如题：  
![在这里插入图片描述][2e417a6f64a24e0c918f5da5a99e6f4b.png]  
可以直观的看出其搜索的过程：**for循环横向遍历，递归纵向遍历，回溯不断调整结果集**，这个理念贯穿整个回溯法系列，也是我做了很多回溯的题目，不断摸索其规律才总结出来的。

优化回溯算法只有剪枝一种方法，在**回溯算法：组合问题再剪剪枝**中把回溯法代码做了剪枝优化，树形结构如图：  
![在这里插入图片描述][1e90c38d67414c8697a53c21b1e4b312.png]  
大家可以一目了然剪的究竟是哪里。

回溯算法：求组合问题！**剪枝精髓是：for循环在寻找起点的时候要有一个范围，如果这个起点到集合终止之间的元素已经不够题目要求的k个元素了，就没有必要搜索了**。

**在for循环上做剪枝操作是回溯法剪枝的常见套路！** 后面的题目还会经常用到。

## 组合总和 ##

### 组合总和（一） ###

在\*\*回溯算法：求组合总和！\*\*中，相当于 \*\*回溯算法：求组合问题！\*\*加了一个元素总和的限制。

树形结构如图：  
![在这里插入图片描述][5abee8ca58bd47ada1e07e89f3e5738b.png]  
整体思路还是一样的，本题的剪枝会好想一些，即：**已选元素总和如果已经大于n（题中要求的和）了，那么往后遍历就没有意义了，直接剪掉**，如图：  
![在这里插入图片描述][3c9c83f7551b414aa0892b1b733c6eee.png]  
在本题中，依然还可以有一个剪枝，就是**回溯算法：组合问题再剪剪枝**中提到的，对for循环选择的起始范围的剪枝。

所以剪枝的代码可以在for循环加上 i <= 9 - (k - path.size()) + 1 的限制！

### 组合总和（二） ###

在**回溯算法：求组合总和（二）中讲解的组合总和问题，和回溯算法：求组合问题！**，\*\*回溯算法：求组合总和！\*\*和区别是：本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。

不少同学都是看到可以重复选择，就义无反顾的把startIndex去掉了。

**本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？**

我举过例子，如果是一个集合来求组合的话，就需要startIndex，例如：**回溯算法：求组合问题！**，**回溯算法：求组合总和！**。

如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：**回溯算法：电话号码的字母组合**。

**注意以上我只是说求组合的情况，如果是排列问题，又是另一套分析的套路**。

树形结构如下：  
![在这里插入图片描述][cf02fb02a61246dca711045845c4165d.png]  
最后还给出了本题的剪枝优化，如下：

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

优化后树形结构如下：

![在这里插入图片描述][4ac38925bef24dea897f44414cdf1e02.png]

### 组合总和（三） ###

在`回溯算法：求组合总和（三)`中集合元素会有重复，但要求解集不能包含重复的组合。

所以难就难在去重问题上了。

这个去重问题，相信做过的录友都知道有多么的晦涩难懂。网上的题解一般就说“去掉重复”，但说不清怎么个去重，代码一甩就完事了。

为了讲解这个去重问题，代码随想录的Carl老师自创了两个词汇，“树枝去重”和“树层去重”。

都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上“使用过”，一个维度是同一树层上“使用过”。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。  
![在这里插入图片描述][e130efaa4222421cb55d1fa3936493b9.png]  
我在图中将used的变化用橘黄色标注上，**可以看出在candidates\[i\] == candidates\[i - 1\]相同的情况下**：

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

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

对于去重，其实排列和子集问题也是一样的道理。

## 多个集合求组合 ##

在**回溯算法：电话号码的字母组合**中，开始用多个集合来求组合，还是熟悉的模板题目，但是有一些细节。

例如这里for循环，可不像是在 **回溯算法：求组合问题！和回溯算法：求组合总和！** 中从startIndex开始遍历的。

因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而**回溯算法：求组合问题！** 和\*\*回溯算法：求组合总和！\*\*都是是求同一个集合中的组合！

树形结构如下：  
![在这里插入图片描述][7127e46e6871404baad9099eb79f6af7.png]  
如果大家在现场面试的时候，一定要注意各种输入异常的情况，例如本题输入1 \* \#按键。

其实本题不算难，但也处处是细节，还是要反复琢磨。

## 切割问题 ##

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

我列出如下几个难点：

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

如果想到了**用求解组合问题的思路来解决 切割问题本题就成功一大半了**，接下来就可以对着模板照葫芦画瓢。

**但后序如何模拟切割线，如何终止，如何截取子串，其实都不好想，最后判断回文算是最简单的了**。

所以本题应该是一个道hard题目了。

除了这些难点，**本题还有细节，例如：切割过的地方不能重复切割所以递归函数需要传入i + 1**。

树形结构如下：  
![在这里插入图片描述][2f4f5e1125e241aeace071bbe66cec36.png]

## 子集问题 ##

### 子集问题（一） ###

在\*\*回溯算法：求子集问题！\*\*中讲解了子集问题，在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果。

如图：  
![在这里插入图片描述][49c9063c44ea46ee83afc9f829c97f0d.png]  
认清这个本质之后，今天的题目就是一道模板题了。

**本题其实可以不需要加终止条件**，因为startIndex >= nums.size()，本层for循环本来也结束了，本来我们就要遍历整棵树。

有的同学可能担心不写终止条件会不会无限递归？

并不会，因为每次递归的下一层就是从i+1开始的。

如果要写终止条件，注意：result.push\_back(path);要放在终止条件的上面，如下：

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

### 子集问题（二） ###

在\*\*回溯算法：求子集问题（二）\*\*中，开始针对子集问题进行去重。

本题就是**回溯算法：求子集问题！** 的基础上加上了去重，去重我们在\*\*回溯算法：求组合总和（三）\*\*也讲过了，一样的套路。

树形结构如下：  
![在这里插入图片描述][71aa6ea91bb04f42a9837ac8af7f7e8a.png]

## 递增子序列 ##

在**回溯算法：递增子序列**中，处处都能看到子集的身影，但处处是陷阱，值得好好琢磨琢磨！

树形结构如下：  
![在这里插入图片描述][668b95d879964ca4bcef5716fb992b82.png]  
很多同学都会把这道题目和\*\*回溯算法：求子集问题（二）\*\*混在一起。

\*\*回溯算法：求子集问题（二）\*\*也可以使用set针对同一父节点本层去重，但子集问题一定要排序，为什么呢？

我用没有排序的集合\{2,1,2,2\}来举个例子画一个图，如下：  
![在这里插入图片描述][c2536719e3114417b2db4395b3847fd7.png]  
相信这个图胜过千言万语的解释了。

## 排列问题 ##

### 排列问题（一） ###

\*\*回溯算法：排列问题！\*\*又不一样了。

排列是有序的，也就是说 \[1,2\] 和 \[2,1\] 是两个集合，这和之前分析的子集以及组合所不同的地方。

可以看出元素1在\[1,2\]中已经使用过了，但是在\[2,1\]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。

如图：  
![在这里插入图片描述][a66b57271fac47b7a9d0ebb923b66b5f.png]  
**大家此时可以感受出排列问题的不同**：

*  每层都是从0开始搜索而不是startIndex
 *  需要used数组记录path里都放了哪些元素了

### 排列问题（二） ###

排列问题也要去重了，在`回溯算法：排列问题（二）`中又一次强调了“树层去重”和“树枝去重”。

树形结构如下：  
![在这里插入图片描述][38e0f5067f5448a7830f80cd2c5c4167.png]  
这道题目神奇的地方就是`used[i - 1] == false也可以，used[i - 1] == true`也可以！

我就用输入: \[1,1,1\] 来举一个例子。

树层上去重(used\[i - 1\] == false)，的树形结构如下：  
![在这里插入图片描述][652e2c9b7ae74fc79593c9aeaeadd1d7.png]  
树枝上去重（used\[i - 1\] == true）的树型结构如下：  
![在这里插入图片描述][6a52cc5c85294da0893b7b542df02166.png]  
**可以清晰的看到使用(used\[i - 1\] == false)，即树层去重，效率更高！**

本题used数组即是记录path里都放了哪些元素，同时也用来去重，一举两得。

## 去重问题 ##

以上我都是统一使用used数组来去重的，其实使用set也可以用来去重！

在**本周小结！（回溯算法系列三）续集**中给出了子集、组合、排列问题使用set来去重的解法以及具体代码，并纠正一些同学的常见错误写法。

同时详细分析了 使用used数组去重 和 使用set去重 两种写法的性能差异：

**使用set去重的版本相对于used数组的版本效率都要低很多**，大家在leetcode上提交，能明显发现。

原因在**回溯算法：递增子序列**中也分析过，主要是因为程序运行的时候对unordered\_set 频繁的insert，unordered\_set需要做哈希映射（也就是把key通过hash function映射为唯一的哈希值）相对费时间，而且insert的时候其底层的符号表也要做相应的扩充，也是费时的。

**而使用used数组在时间复杂度上几乎没有额外负担！**

**使用set去重，不仅时间复杂度高了，空间复杂度也高了**，在**本周小结！（回溯算法系列三）** 中分析过，组合，子集，排列问题的空间复杂度都是O(n)，但如果使用set去重，空间复杂度就变成了O(n^2)，因为每一层递归都有一个set集合，系统栈空间是n，每一个空间都有set集合。

那有同学可能疑惑 用used数组也是占用O(n)的空间啊？  
used数组可是全局变量，每层与每层之间公用一个used数组，所以空间复杂度是O(n + n)，最终空间复杂度还是O(n)。

## 重新安排行程（图论额外拓展） ##

之前说过，有递归的地方就有回溯，深度优先搜索也是用递归来实现的，所以往往伴随着回溯。

在**回溯算法：重新安排行程**其实也算是图论里深搜的题目，但是我用回溯法的套路来讲解这道题目，算是给大家拓展一下思路，原来回溯法还可以这么玩！

以输入：\[\[“JFK”, “KUL”\], \[“JFK”, “NRT”\], \[“NRT”, “JFK”\]为例，抽象为树形结构如下：  
![在这里插入图片描述][7237b0bc59fe4bed8e8df90e130f0715.png]  
本题可以算是一道hard的题目了，关于本题的难点我在文中已经详细列出。

**如果单纯的回溯搜索（深搜）并不难，难还难在容器的选择和使用上！**

本题其实是一道深度优先搜索的题目，但是我完全使用回溯法的思路来讲解这道题题目，**算是给大家拓展一下思维方式，其实深搜和回溯也是分不开的，毕竟最终都是用递归**。

## 棋盘问题 ##

### N皇后问题 ###

在**回溯算法：N皇后问题**中终于迎来了传说中的N皇后。

下面我用一个3 \* 3 的棋盘，将搜索过程抽象为一棵树，如图：  
![在这里插入图片描述][6b1aa52d03314142a9ab94e281c306dd.png]  
从图中，可以看出，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。

那么我们用皇后们的约束条件，来回溯搜索这棵树，**只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了**。

如果从来没有接触过N皇后问题的同学看着这样的题会感觉无从下手，可能知道要用回溯法，但也不知道该怎么去搜。

**这里我明确给出了棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了**。

相信看完本篇**回溯算法：N皇后问题**也没那么难了，传说已经不是传说了。

### 解数独问题 ###

在**回溯算法：解数独**中要征服回溯法的最后一道山峰。

解数独应该是棋盘很难的题目了，比N皇后还要复杂一些，但只要理解 “二维递归”这个过程，其实发现就没那么难了。

下面的回溯法题目，例如：77.组合（组合问题） ，131.分割回文串（分割问题） ，78.子集（子集问题），46.全排列（排列问题），以及51.N皇后（N皇后问题），其实这些题目都是一维递归。

其中N皇后问题是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来遍历列，然后一行一列确定皇后的唯一位置。

本题就不一样了，**本题中棋盘的每一个位置都要放一个数字，并检查数字是否合法，解数独的树形结构要比N皇后更宽更深**。

因为这个树形结构太大了，我抽取一部分，如图所示：  
![在这里插入图片描述][27d866b05a964b85b34a52e33bb1687c.png]  
解数独可以说是非常难的题目了，如果还一直停留在一维递归的逻辑中，这道题目可以让大家瞬间崩溃。

所以在**回溯算法：解数独**中就用到了二维递归。

一波分析之后，在看代码会发现其实也不难，唯一难点就是理解**二维递归**的思维逻辑。

## 性能分析 ##

关于回溯算法的复杂度分析在网上的资料鱼龙混杂，一些所谓的经典面试书籍不讲回溯算法，算法书籍对这块也避而不谈，感觉就像是算法里模糊的边界。

以下在计算空间复杂度的时是把系统栈（不是数据结构里的栈）所占空间算进去。

### 子集问题分析 ###

**1. 时间复杂度**：`O(2^n)`，因为每一个元素的状态无外乎取与不取，所以时间复杂度为`O(2^n)`

**2. 空间复杂度**：`O(n)`，递归深度为n，所以系统栈所用空间为`O(n)`，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为`O(n)`

### 排列问题分析 ###

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

**2. 空间复杂度**：O(n)，和子集问题同理。

### 组合问题分析 ###

**1. 时间复杂度**：O(2^n)，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。

**2. 空间复杂度**：O(n)，和子集问题同理。

### N皇后问题分析 ###

**1. 时间复杂度**：O(n!) ，其实如果看树形图的话，直觉上是O(n^n)，但皇后之间不能见面所以在搜索的过程中是有剪枝的，最差也就是O（n!），n!表示`n * (n-1) * .... * 1`。

**2. 空间复杂度**：O(n)，和子集问题同理。

### 解数独问题分析 ###

**1. 时间复杂度**：`O(9^m)` , m是’.'的数目。  
**2. 空间复杂度**：`O(n^2)`，递归的深度是`n^2`。

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

## 总结 ##

*  如何理解回溯法的搜索过程？
 *  什么时候用startIndex，什么时候不用？
 *  如何去重？如何理解“树枝去重”与“树层去重”？
 *  去重的几种方法？
 *  如何理解二维递归？

![在这里插入图片描述][5d9e7bb774b746a09238c022290fff86.png]  
**参考资料**：[代码随想录-回溯总结篇][-]

[2e417a6f64a24e0c918f5da5a99e6f4b.png]: https://img-blog.csdnimg.cn/2e417a6f64a24e0c918f5da5a99e6f4b.png
[1e90c38d67414c8697a53c21b1e4b312.png]: https://img-blog.csdnimg.cn/1e90c38d67414c8697a53c21b1e4b312.png
[5abee8ca58bd47ada1e07e89f3e5738b.png]: https://img-blog.csdnimg.cn/5abee8ca58bd47ada1e07e89f3e5738b.png
[3c9c83f7551b414aa0892b1b733c6eee.png]: https://img-blog.csdnimg.cn/3c9c83f7551b414aa0892b1b733c6eee.png
[cf02fb02a61246dca711045845c4165d.png]: https://img-blog.csdnimg.cn/cf02fb02a61246dca711045845c4165d.png
[4ac38925bef24dea897f44414cdf1e02.png]: https://img-blog.csdnimg.cn/4ac38925bef24dea897f44414cdf1e02.png
[e130efaa4222421cb55d1fa3936493b9.png]: https://img-blog.csdnimg.cn/e130efaa4222421cb55d1fa3936493b9.png
[7127e46e6871404baad9099eb79f6af7.png]: https://img-blog.csdnimg.cn/7127e46e6871404baad9099eb79f6af7.png
[2f4f5e1125e241aeace071bbe66cec36.png]: https://img-blog.csdnimg.cn/2f4f5e1125e241aeace071bbe66cec36.png
[49c9063c44ea46ee83afc9f829c97f0d.png]: https://img-blog.csdnimg.cn/49c9063c44ea46ee83afc9f829c97f0d.png
[71aa6ea91bb04f42a9837ac8af7f7e8a.png]: https://img-blog.csdnimg.cn/71aa6ea91bb04f42a9837ac8af7f7e8a.png
[668b95d879964ca4bcef5716fb992b82.png]: https://img-blog.csdnimg.cn/668b95d879964ca4bcef5716fb992b82.png
[c2536719e3114417b2db4395b3847fd7.png]: https://img-blog.csdnimg.cn/c2536719e3114417b2db4395b3847fd7.png
[a66b57271fac47b7a9d0ebb923b66b5f.png]: https://img-blog.csdnimg.cn/a66b57271fac47b7a9d0ebb923b66b5f.png
[38e0f5067f5448a7830f80cd2c5c4167.png]: https://img-blog.csdnimg.cn/38e0f5067f5448a7830f80cd2c5c4167.png
[652e2c9b7ae74fc79593c9aeaeadd1d7.png]: https://img-blog.csdnimg.cn/652e2c9b7ae74fc79593c9aeaeadd1d7.png
[6a52cc5c85294da0893b7b542df02166.png]: https://img-blog.csdnimg.cn/6a52cc5c85294da0893b7b542df02166.png
[7237b0bc59fe4bed8e8df90e130f0715.png]: https://img-blog.csdnimg.cn/7237b0bc59fe4bed8e8df90e130f0715.png
[6b1aa52d03314142a9ab94e281c306dd.png]: https://img-blog.csdnimg.cn/6b1aa52d03314142a9ab94e281c306dd.png
[27d866b05a964b85b34a52e33bb1687c.png]: https://img-blog.csdnimg.cn/27d866b05a964b85b34a52e33bb1687c.png
[5d9e7bb774b746a09238c022290fff86.png]: https://img-blog.csdnimg.cn/5d9e7bb774b746a09238c022290fff86.png
[-]: https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html#%E5%9B%9E%E6%BA%AF%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80