回溯法理论基础

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

解决问题

不止本章的练习，回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。
回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。
回溯算法能解决如下问题：

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

在刷回溯算法也根据以上问题顺序刷，过程中回溯法确实不好理解，所以需要把在写代码前画画图，把回溯法抽象为一个图形来理解就容易多了。（在画图过程中还可以切实知道如何更好剪枝，减去没必要的步骤。干想还是比较困难的）

引用李强总理的一句话：坐在办公室碰到的都是问题，深入基层看到的全是办法。

（第一章第一题77 组合中一层层递归以及for循环去画，了解程序怎么走的，对后面做题非常有帮助）

回溯模板

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

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

此模板伴随整个回溯法系列！

组合问题

回溯算法第一题就是77 组合——组合问题。
文章举例了k层for循环例子，进而得出都是同样是暴力解法，为什么要用回溯法！它用递归控制for循环嵌套的数量
本题把回溯问题抽象为树形结构，如题：

程序运转顺序：

可以直观的看出其搜索的过程：for循环横向遍历，递归纵向遍历，回溯不断调整结果集，这个理念贯穿整个回溯法系列。

另外，优化回溯算法只有剪枝一种方法，在77 组合 – 剪枝优化中把回溯法代码做了剪枝优化，树形结构如图：

大家可以一目了然剪的究竟是哪里。
剪枝精髓是：for循环在寻找起点的时候要有一个范围，如果这个起点到集合终止之间的元素已经不够题目要求的k个元素了，就没有必要搜索了。

在for循环上做剪枝操作是回溯法剪枝的常见套路！

组合总和

组合总和（一）

在216 组合总和Ⅱ中，相当于 77 组合问题多加了一个元素总和的限制。
树形结构如图（注意红色部分）：
整体思路还是一样的，本题的剪枝会好想一些，即：
已选元素总和如果已经大于n（题中要求的和）了，那么往后遍历就没有意义了，直接break剪掉，如图（注意蓝字）：

本题另一个剪枝，就是77 组合 – 剪枝优化中提到的，对for循环选择的起始范围的剪枝。
所以剪枝的代码可以在for循环加上** i <= 9 – (k – path.size()) + 1** 的限制！

组合总和（二）

相较77 组合以及 216 组合总和Ⅱ，本题39 组合总和的特点是可重复使用元素，但是有总和的限制。（所以间接的也是有个数的限制）
看到可以重复选择，把startIndex去掉可以吗？
不可以！本题为从单个集合中取元素，因此还需要startIndex来控制for循环的起始位置！

回到正题，本题的树形结构如下：

最后还给出了本题的剪枝优化（之和大于targetSum），如下：

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

优化后树形结构如下（注意蓝字）：

组合总和（三） – 去重

去重问题来啦！在40 组合总和Ⅱ中要求集合元素会有重复，但组合不能重复。因此难就难在去重问题上了。
都知道组合问题可以抽象为树形结构，那么**“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上“使用过”，一个维度是同一树层上“使用过”**。
理解这两个层面上的“使用过” 对去重问题很重要

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

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

类似的排列和子集问题的去重也是一样的道理。

多个集合求组合

在17 电话号码的字母组合中，开始用多个集合来求组合，还是熟悉的模板题目，但是有一些细节。
由于是从多个集合中取值，这里for循环不同于 77 组合和 216 组合总和Ⅱ 从startIndex开始遍历的。
本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而 77 组合和 216 组合总和Ⅱ 都是是求同一个集合中的组合！
树形结构如下：

另外还要注意各种输入异常的情况，例如本题输入1 * #按键。

⭕对于组合问题，什么时候需要startIndex呢？

如果是在一个集合里选的话，就需要startIndex，例如：77 组合，216 组合总和Ⅱ。
如果是在多个集合里选取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17 电话号码的字母组合

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

切割问题

在131 分割回文串中，开始遇到切割问题，虽然回溯算法看起来都是一道模板题，但是正在写起来会遇到很多细节性的难点。

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

切割问题其实类似组合问题：用求解组合问题的思路来解决切割问题本题就成功一大半了，接下来就可以对着模板照葫芦画瓢。
如何模拟切割线：我们会发现每次循环后刚好startIndex都会往后移一位，每次递归就会在一个新的startIndex上继续循环。因此可以把startIndex作为分割线
切割问题中递归如何终止：startIndex切到最后
如何判断回文：双指针章节有刷过，头尾指针向中靠拢，判断是否相等。
在递归循环中如何截取字串：如果是合法字符后，使用string自带的substring方法切割（注意其下标）

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

子集问题

子集问题（一）

在78 子集中，在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果。
如图（收集红线部分）：

认清这个本质之后，今天的题目就是一道模板题了。
由于每个节点都需要返回，所以不需要加终止条件，在for循环中startIndex >= nums.size()后就结束了。
而递归中，每次传参传入i + 1，也会终止~

子集问题（二） – 去重

**去重问题来了！**在90 子集Ⅱ中，开始针对子集问题进行去重。
本题就是78 子集的基础上加上了去重，而去重在40 组合总和Ⅱ也碰过了，需要避免树层重复元素，一样的套路。
树形结构如下（注意看蓝字 – 树层重复与树枝重复）：

递增子序列

在491 递增子序列中，处处都能看到子集的身影，但处处是陷阱！
一开始以为是和之前去重一样，先排序后设定used数组的false true，这就掉坑了~
由于本题在原数组基础上求递增子序列，因此排序会打乱原数组下标，得到不同答案。
树形结构如下：

另外，子集是一定需要排序后才去重的。而且子集没要求保留原数组的下标，也满足排序条件
如果没有排序的集合{2,1,2,2}画一个图，如下：

排列问题

排列问题（一）

排列问题46 全排列又不一样了。
排列是有序的，也就是说** [1,2] 和 [2,1] 是两个集合**，这和之前分析的子集以及组合所不同的地方。因此也不需要使用startIndex来避免元素重复的问题，只需要用used数组标记哪个数组用过，用于遍历剩余集合。

如图（注意橙色的used数组）：

大家此时可以感受出排列问题的不同：

每层都是从0开始搜索而不是startIndex
取而代之的用used数组记录path里都放了哪些元素

排列问题（二） – 去重

去重问题又又又来了！这次是排列问题，在47 全排列Ⅱ中又一次强调了“树层去重”和“树枝去重”。
树形结构如下：

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

去重问题

以上我都是统一使用used数组来去重的，其实使用set也可以用来去重！
但是在性能上，数组更优秀。
因为程序运行的时候对set 频繁的add，set需要做哈希映射（也就是把key通过HashCode映射为唯一的哈希值）相对费时间，而且add的时候其底层的符号表也要做相应的扩充，也是费时的。
而使用used数组在时间复杂度上几乎没有额外负担！
使用set去重，不仅时间复杂度高了，空间复杂度也高了，在组合，子集，排列问题的空间复杂度都是O(n)，但如果使用set去重，空间复杂度就变成了O(n^2)，因为每一层递归都有一个set集合，系统栈空间是n，每一个空间都有set集合。

但是用used数组也是占用O(n)的空间啊？

used数组可是全局变量，每层与每层之间公用一个used数组，所以空间复杂度是O(n + n)，最终空间复杂度还是O(n)。

性能分析

以下在计算空间复杂度的时候我都把系统栈（不是数据结构里的栈）所占空间算进去。
子集问题分析：

时间复杂度：O(2n)，因为每一个元素的状态无外乎布尔值，取与不取，所以时间复杂度为O(2n)
空间复杂度：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(2n)，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。
空间复杂度：O(n)，和子集问题同理。

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

进阶的N皇后问题，解数独、重新安排行程见这里?

总结

根据前面所做的可以总结以下经验：

首先写代码前，用树形结构完整画出图，看看应该会怎么遍历？
- “坐在办公室碰到的都是问题，深入基层看到的全是办法。”
观察树形结构
- 终止条件是什么？
- 各层递归后从哪里开始（0 or startIndex）
- 需不需要去重（树层上有没有重复元素）
  - 可以排序 – 判断used [i – 1] ?= used [i] && used[i – 1] ?= false
  - 不能排序 – 如果有限范围用used[xx] 标记如果无限范围只能用HashSet了
  - 单纯不能重复 – (排序题)new used[nums.length] 使用了就设置为true
- 能不能剪枝？（排序后如果sum已经大于targetSum 后面没必要去遍历 break）