回溯法理论基础

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

处理问题

不止本章的练习，回溯法也常常和二叉树遍历，深度优先查找混在一同，由于这两种方法都是用了递归。
回溯法便是暴力查找，并不是什么高效的算法，最多再剪枝一下。
回溯算法能处理如下问题：

• 组合问题：N个数里边按必定规矩找出k个数的调集
• 摆放问题：N个数按必定规矩全摆放，有几种摆放方法
• 切开问题：一个字符串按必定规矩有几种切开方法（相似于组合问题）
• 子集问题：一个N个数的调集里有多少契合条件的子集
• 棋盘问题：N皇后，解数独等等（此部分较难）

在刷回溯算法也依据以上问题顺序刷，过程中回溯法的确不好了解，所以需求把在写代码前画画图，把回溯法笼统为一个图形来了解就简单多了。（在画图过程中还能够实在知道怎样更好剪枝，减去没必要的过程。干想仍是比较困难的）

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

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

回溯模板

void backtracking(参数) {
    if (停止条件) {
        寄存成果;
        return;
    }
    for (挑选：本层调会集元素（树中节点孩子的数量便是调集的大小）) {
        处理节点;
        backtracking(途径，挑选列表); // 递归
        回溯，吊销处理成果
    }
}

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

组合问题

组合问题

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

能够直观的看出其查找的过程：for循环横向遍历，递归纵向遍历，回溯不断调整成果集，这个理念贯穿整个回溯法系列。

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

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

组合总和

组合总和（一）

在216 组合总和Ⅱ中，相当于 77 组合问题 多加了一个元素总和的约束。
树形结构如图（留意红色部分）：

组合总和（二）

相较77 组合 以及 216 组合总和Ⅱ，本题39 组合总和的特点是可重复运用元素，但是有总和的约束。（所以间接的也是有个数的约束）
看到能够重复挑选，把startIndex去掉能够吗？
不能够！本题为从单个调会集取元素，因而还需求startIndex来操控for循环的开端位置！

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

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

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

组合总和（三） – 去重

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

• used[i – 1] == true，阐明同一树枝candidates[i – 1]运用过
• used[i – 1] == false，阐明同一树层candidates[i – 1]运用过

相似的摆放和子集问题的去重也是相同的道理。

多个调集求组合

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

⭕对于组合问题，什么时分需求startIndex呢？

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

留意以上只针对求组合的状况，假如是摆放问题，又是另一套剖析的套路。

切开问题

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

• 切开问题其实相似组合问题
• 怎样模仿切开线
• 切开问题中递归怎样停止
• 在递归循环中怎样截取子串
• 怎样判别回文

切开问题其实相似组合问题：用求解组合问题的思路来处理 切开问题本题就成功一大半了，接下来就能够对着模板照葫芦画瓢。
怎样模仿切开线：我们会发现每次循环后刚好startIndex都会往后移一位，每次递归就会在一个新的startIndex上继续循环。因而能够把startIndex作为切开线
切开问题中递归怎样停止：startIndex切到最终
怎样判别回文：双指针章节有刷过，头尾指针向中挨近，判别是否相等。
在递归循环中怎样截取字串：假如是合法字符后，运用string自带的substring方法切开（留意其下标）

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

子集问题

子集问题（一）

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

子集问题（二） – 去重

**去重问题来了！**在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）

学习材料：

回溯算法总结篇