1.回溯函数模板返回值以及参数
回溯函数名：backtracking
返回值：一般为 void
1.参数：（1）要遍历哪个数组或者字符串（2）在下一层 for 循环中遍历的起始位置在哪
2.回溯函数终止条件
3.回溯搜索的遍历过程
模板
上面的代码还能进一步细化
**for 循环的 i++ 就是横向遍历树，每次递归 backtracking 就是纵向遍历树 **
1.path 的长度不是固定的
2.每次怎么选取元素
1.3.1 子集问题的时空复杂度
1.3.2 排列问题的时空复杂度
时间复杂度： O(n!)
在最外层 for 循环一共会遍历 n 个节点，这 n 个节点每向下一层， startIndex 的值传入是 i+1，在这一层遍历 n-1 次，再向下一层遍历 n-2 次
对于一个节点来说最终的遍历次数就是 (n-1)x(n-2)。。。，一共有 n 个节点， 最终结果是 O(n!)
1.3.3 组合问题的时空复杂度
时间复杂度：O(n*2^n)
组合问题其实是一个结果集合变长的选择问题，所以同选择问题一样，时间复杂度是 O(n*2^n)
空间复杂度：
S1：将集合放在树根
S2：不断的向下扩展，更新 startIndex 和 i 的值。
对于这个树来说横向看 i 的个数不断在 +1 ，纵向看 i 的值是不变的，就是 for 循环 i 的起始值。
有两种方法会退出此 backtracking :
①终止条件生效 return 的时候
这个时候会返回到调用他的那一个横条
2.1.2 C++ 代码实现
2.1.3 Python 代码实现
2.1.4 剪枝操作
k-path.size() ：还有多少个值没有处理
n-(k-path.size())+1：最后一次处理的是哪个值，这个值后面的元素都不用再处理了
比如对于 [1,2,3,4] 来说，第二轮应该再开始遍历 2 ，但是 2 其实是不用判断的，所以在 for 循环条件中
startIndex = 2,i<=4-（4-0）+1 这个时候 for 循环就不满足要求了
所以剪枝后的 for 循环就变为了：
这个题和上面那个题思路完全一样，只不过这里在 backtracking 的时候还要有进一步的判断，当 sums 不满足 n 的时候就不将 path 添加到 res 中
被遗忘的剪枝操作：
这里不仅仅在 for 循环中进行剪枝，当 sums>targetSums 也要进行剪枝
2.2.2 C++ 代码实现
妙
这里对 sums 进行减的操作还是很妙的
2.3.1 算法描述
首先先想如何用暴力的方式进行解决，将本题的手机按键进行简化，假设说现在只有两个字符串
那么在遍历的时候就会有双重 for 循环
字符串少还好说，但是如果字符串很多就要 n 重 for 循环，所以为了减少 for 循环的嵌套使用回溯的方式进行解决
1.这里的 index 用于判断当前处理的是 digits 中哪个元素，所以在下一层 backtracking 的时候应该将 index+1 传入下一个元素
2.对于 digits 进行判空操作
2.3.3 知识扩展
如何将 string 类型的数字转换为 int 类型
2.4.1 算法描述
先将数组进行排序；
横向数组取值的时候不能包含上面的元素，但是纵向可以包含上面的重复元素
相关剪枝操作：
如果本层的 sum 也就是 sum+candidates[i] 已经大于 target ，就可以结束 for 循环遍历
这个题的结束条件不一样，结束条件 sum==target 就结束对当前数字的判断
2.4.2 C++ 代码实现
易错点：
1.不要忘记给集合排序
如果不排序很可能在一个前面就 return ，后面的数就不能判断了
2.backtracking 是否要传入 startIndex 的问题，这个值需要传多大
3.这里操作的是 candidates[i] 不直接值 i 了
2.4.3 相关知识
1.C++ 如何对数组排序
2.5.1 算法描述
这里的 index=0 是 value =1，index=1，value=1，两个值重复。在最外层 for 循环中，当对 index=0 判断了就不用再对 index=1 再进行判断了
去重去掉的是“同一树层上使用过的元素”
关键：当判断 index=0 之后的元素时，如果 cur 的值等于 cur-1 的值，则这个数直接跳过
这句话不会影响到后面的拼接，比如说 [1,2,2,2] 这里有 3 个 2 ，在对 2 计算完子集后不会再对后面两个 2 计算子集，但是第一个 2 子集的结果是包含后两个 2 的，因为这里只对 i-1 进行判断，对 i+1 是没有影响的
2.5.2 C++ 代码实现
input："aab’’
output：[ [“aa”,“b”], [“a”,“a”,“b”] ]
回文串+回溯
2.6.1 算法描述
需要注意的是 for 循环每次取的时候还是取一个字符，但是在判断回文的时候一次会放入多个字符
第一次指向 a ，剩余 ab
第一层循环：指向 a（第二个），这时候 path 当中是有一个 a 的
第三层循环：指向 b
第二次指向 a ，说明这次要判断 aa，剩余 b ，只能再切分 b
第三次指向 b ,没有办法继续被切分，直接判断 aab
如何生成 [[“a”,“a”,“b”]]
startIndex = 0 , i = 0 path = “a”
startIndex = 1 , i = 1 截取字符串是从 1 开始的 path =“a”
startIndex = 2,i=2 ,截取字符串从 2 开始，截取一个 path =“b”
如何生成 [[“aa”,“b”]]
startIndex = 0, i = 1 str = aa
2.6.2 代码实现
2.6.4 知识扩展
1.如何判断是回文字符串
2.7.1 算法概述
1.终止条件
当 pointNum = 3 也就是 ‘.’ 的个数等于 3 的时候就不用再继续判断了。在打了 3 个 . 后还要判断最后一段，然后再将 s 放入 res
2.递归参数
startIndex 用于指向下一个打 ‘.’ 的地方
3.单层搜索逻辑
在判断一个 IP 地址的时候 ‘.’ 要一位一位的加。
就拿上面的字符串举例，在 2 后面加一个 ‘.’ , 在 5 后面加一个 ‘.’ ，这样一个个的判断，如下面所示
[“2.5.5.25511135”,“2.5.52.5511135”,“2.5.525.511135”,“2.5.5255.11135”,“2.5.52551.1135”,“2.5.525511.135”,“2.5.5255111.35”,“2.5.52551113.5”,“2.55.2.5511135”,“2.55.25.511135”,“2.55.255.11135”,“2.55.2551.1135”,“2.55.25511.135”,“2.55.255111.35”,“2.55.2551113.5”,“2.552.5.511135”,“2.552.55.11135”,“2.552.551.1135”,“2.552.5511.135”,“2.552.55111.35”,“2.552.551113.5”,“2.5525.5.11135”,“2.5525.51.1135”,“2.5525.511.135”,“2.5525.5111.35”,“2.5525.51113.5”,“2.55255.1.1135”,“2.55255.11.135”,“2.55255.111.35”,“2.55255.1113.5”,“2.552551.1.135”,“2.552551.11.35”,“2.552551.113.5”,“2.5525511.1.35”,“2.5525511.13.5”,“2.55255111.3.5”,“25.5.2.5511135”,“25.5.25.511135”,“25.5.255.11135”,“25.5.2551.1135”,“25.5.25511.135”,“25.5.255111.35”,“25.5.2551113.5”,“25.52.5.511135”,“25.52.55.11135”,“25.52.551.1135”,“25.52.5511.135”,“25.52.55111.35”,“25.52.551113.5”,“25.525.5.11135”,“25.525.51.1135”,“25.525.511.135”,“25.525.5111.35”,“25.525.51113.5”,“25.5255.1.1135”,“25.5255.11.135”,“25.5255.111.35”,“25.5255.1113.5”,"25.52551.1.1…
2.7.2.C++ 代码实现
2.7.3 知识扩展
1.如何判断合法 IP 地址段
首先判断：
①start 指针和 end 指针的位置是否不合法
②字段开头是不是 0 元素
③完成上面步骤后进入 for 循环
判断这个字符是否是数字
判断 IP 地址是否在 255 之内
2.7.1 算法描述
本算法是求每个元素的子集，并且子集中的元素是没有重复的
此处有图
关键点：
1.每一个叶子节点都要添加到 res ，所以要在每一次遍历 backtracking 的时候将结果进行添加，平常都是到了最后才添加
2.path 的长度每增加 1 都会进入一个 for 循环
3.每一次 for 循环结束后 i++ 退出到上一层 for 循环
2.7.2 C++ 代码实现
2.8.1 算法描述
本题的关键点就是求子集，然后不重复，不重复的话在 40 组合2 已经涉及到了，而求子集又是上一题的思路
2.8.2 C++ 代码实现
易错点：
最后别忘了对 vector 进行排序
2.9.1 算法描述
1.这个题和以往求子序列有两点不同：
path 内的子集需要递增，candidate 是无序的
①要想组成 path 这里的条件是 path 中的顺序必须是递增的，所以要判断 nums[i] 和 path[i-1] 是否是递增的
②判断 nums[i] 是否在整个 candidate 中出现过，因为 candidate 不是顺序的，所以需要用 set 进行判断，如果用 nums[i-1] 和 nums[i] 的判断，必须保证 candidate 有序
这里产生重复是因为树的横向产生重复，所以在每一层 for 循环最外面增加 set 进行去重判断
比如 [4,7,6,7] 如果 [7] 已经判断完 ,[7] 就不能再出现了
容器的选择：
这里有两种方法，第一种是用哈希表，第二种是用数组，但是当数据比较少的时候，数组的速度比哈希表快很多
手模树：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZDSnIndc-1644592316406)(https://gitee.com/xuboluo/images/raw/master/img/202202062340021.png)]
2.9.2 C++ 算法实现
1.数组实现
2.Hash 实现
2.9.4 知识扩展
1.得到 vector的最后一个元素
如何判断它是一个递增序列：
将nums 当前值和 path 最后一个值进行比较
2.使用 Set 的方法如何判断这个值之前是否被判断过
这里使用 nums 中的值当做 valus,key 值是通过 hash 表映射得到的
①先找到 nums[i] 保存的 index
②然后找到uset.end() ，因为前面已经判断了是否是递增序列，所以只要判断最后一个元素即可
find 方法是根据 value 的值返回某个元素的下标
3.Set 的初始化什么时候写在 for 循环里面什么时候写在 for 循环外面
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jWKBVRJ6-1644592316406)(/Users/xuguagua/Documents/typora_image/image-20211030205435981.png)]
就像这个题，我们不在乎嵌套 for 循环的时候后面的 7 会不会被拼接上，就比如其中一个答案 [4,7,7]
当集合第一个7 的时候，其后面还是可以接 7 的
但是答案只有一个 [7,7] 也就是说在最外层 for 循环是不允许集合两次 7 的。所以在最外层 for 循环迭代的时候，只能操作一个 7
所以在组外层 for 循环 set 的值是不能重复的
而 46 题全排列这个题是在内层嵌套时是不能重复的，所以要把这个 set 定义在每一次 backtracking 的时候
最后选择 set 初始化位置时要看是 path 内不允许有重复还是 path 之间不允许有重复
2.10_46 全排列
2.10.1 算法描述
关键点：
[1,2,3] 和 [1,3] 都 比较容易得到，但是 [1,3,2] 怎么得到，所以就不能使用 startIndex 作为 i 的开始了。
相当于添加了 3 之后又添加了 2 ，但是 i 要从 0 开始，但是重复出现的 1 又是怎么过滤掉的
解决方法：
为了将 1 过滤需要使用一个 used 数组
在 path 进行 pop 的时候需要将 used 的元素设为 false
错误思路：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-umGlQr4M-1644592316406)(https://gitee.com/xuboluo/images/raw/master/img/202202062340059.png)]
正确思路：
2.10.2 C++ 代码实现
因为这里 nums 中存储的元素个数并不多，所以使用数组存储每一个元素的使用用情况
2.11.1 算法描述
每一层 for 循环嵌套里面值不能重复：
used[i] = false
有两种东西不能重复：
① 在同一层 for 循环中，如果 nums[i-1] 和 nums[i] 重复，则 nums[i-1] 不判断了 —>nums[i-1]!=nums[i]
② 在递归过程中，i 从 0 开始，path 中如果重复放入则 nums[i] 就不再放了 —> used
2.11.2 C++代码实现
2.12.1 算法描述
行程重复的情况：
再从 JFK 出发可以去 ATL 和 SFO ，因为 ATL 排序小所以 JFK 去 ATL ，但是又可以从 ATL 返回到 JFK ，然后又从 JFK 到 ATL 这样就会出现一种无限循环的方式，需要一个记录机票使用次数的 int 变量
1.终止条件
当存放结果的数组 res 中形成个数 = 机票个数 + 1 ，就说明所有的机票都使用过一次了
2.bool 类型的 backtracking
3.数据结构
这里是用的数据结构为 ,其中
①里面用 map 而不用 unordered_map 的原因是 map 是顺序的，可以通过字母顺序对机场进行排序
②这里用 map 而不用 set 是因为 set 无法记录次数，如果不能记录次数容易出现死循环
记录航班次数的原因是判断这条线路之前是否走过，每走一次里面的值就会-1
大于 0 ：没有走过
小于0：走过
可以理解为还有几张剩余的
关键代码：
头尾相接
执行 for 循环中的方法 result 就将 MUC 拼接在最后
for 循环的条件就可以根据 MUC 找到以 MUC 为 key 值的 value
一直往下一直往下头尾相接
为什么是 bool 值的 backtracking
举例：
[[“JFK”,“KUL”],[“JFK”,“NRT”],[“NRT”,“JFK”]]
这里判断结束的条件不是通过子集合的元素个数，而是根据是这个飞行路线是否是通的。
如果在 backtracking 中发现这个路线可以走通则直接 return true
如果发现某个地点走不通，比如上面的 KUL ，则需要将 KUL pop 出来
4.整体步骤
（1）形成 sour->(target,num) 的映射，用来记录出发地目的地以及走的次数
（2）在 backtracking 中根据首尾相接原则不断找到下一个要判断的地点
2.12.2 C++ 代码实现
2.13.1 算法描述
N 皇后一共有三个要求：
1.不能同行
2.不能同列
3.不能同斜线：正对角线和副对角线
整体思路就是去试每一个位置上的元素是否符合三个要求。上图所示每一层都是 for 循环的循环变量+1，每一列都会嵌套一层 for 循环。下面只对上图 ①②③④ 四个棋盘进行讲解
棋盘①
row = 0 ;col = 0; isValid 三个 for 循环全部略过，所以这个方法返回 true ,Q 被写在了 [0] [0] 的位置上；这时候嵌套一层 for 循环，并将 row+1 的值传入，说明这一行已经判断完了
棋盘②
row=1;col=0,也就是判断 [1] [0]下标的这个位置是否可行；调用 isValid 方法，这个方法中判断的是同列是否有相同元素，因为同行是在同一层 for 循环进行判断的。对于同列进行判断二维下标：【变化】【固定】即可判断同一列的不同行是否有重复。因为这里产生重复所以返回 false ，就不对这个位置进行任何赋值。
棋盘③
row=1；col=1 ，因为 ② 不可行所以向下判断下一个格子。由上可知同列的不同行是没有重复元素的，所以先判断 45 度对角线。就用③的这个 Q 进行判断，起始判断的位置肯定不是它自己现在的位置，是①的位置，所以一开始先进行两个减1 的操作，然后再判断对应的位置是否有 Q 。
棋盘④
row=1;col=3,是接茬棋盘③的同一个 for 循环执行的
棋盘⑤
row=2;col=1 是从棋盘 ④的位置嵌套的 for 循环，这里判断的是 145 度角，副对角线，判断的第一个位置就是它右斜上方的 Q ，其他判断不变
棋盘⑥
起始在棋盘⑤的时候 row 的值就是 n 了，其实棋盘⑥是没有判断的
1.如何判断主对角线和副对角线
起始位置是当前元素所对应对角线的位置，该位置的后侧都是没有元素的，所以只需要判断上侧
2.isValid 同行同列方法中每次判断的都是相同列中不同行是否一致
3.res.push_back(chessboard); 有几种排棋方法，这个就会被执行多少次
chessboard 保存一种可能性
4.这里的 isValid 操作只是判断当前情况下是否满足三个条件，也许在下一个 row 就不满足了
N 皇后判断代码：
易错点：
①只要判断该位置所在列是否满足，不用判断所在行，因为棋子在判断的时候是横向走的，该位置之前的格子一定没有棋子
②判断 45 和 135 度角的时候判断的下标要是 Q 经历过的下标，没经历的下标不用判断
③为什么 chessboard 放置在递归中
因为有多种棋盘的情况，每一种棋盘的情况都是互不干扰的
2.13.2 C++ 代码实现
2.13.3 知识扩展
1.创建一个棋盘
2.14.1 算法描述
1.关于嵌套 for 循环的个数
这里是一个二维棋盘，所以每判断一个值要是用双重 for 循环，用于定位行列。与此同时，每一个格子都要判断 1-9 哪个值合适，所以还要再嵌套一个 for 循环去判断每一个格子；那么对于这个格子就是用三重 for 循环进行一次递归
2.判断是否是数独要满足三点：
判断是数独的话需要每一次对二维棋盘中每一个点进行判断，判断是否是数独的条件是该值是否和在这一行或者这一例或者九宫格中出现过
（1）固定行，判断每一列是否是数独
（2）固定列，判断每一行是否是数独
（3）每段每一个小的 3*3 的格子是否是数独
3.关于 return 与终止循环的条件
这里是需要回溯的反馈结果的，使用三重 for 循环填完一个值，但是这个值不一定就确定下来，还要通过后面的判断结果对这个值进行反馈
所以 backtracking 是 bool 类型的，需要有3个地方返回 return 的结果：
①在 9 个 k 值全部判断完后没有合适的字符，则返回 false
②在三个 for 循环全部都判断完后返回 true
③每次递归时接收 backtracking 的结果:这个 true 代表后面的数字结果也是成功的
2.14.2C++ 代码实现
易错：
注意所有 return 的位置和值
LeetCode 题目链接
3.1.1 算法描述
回溯+Hash
1.回溯问题
从题目最后的输出结果看出让输出某个数字组合的全部组成答案，这个就必须对每个数字进行一个个的遍历判断。所以用到回溯
2.HashMap
解决重复问题：
测试用例：[2,2,8,8,2]
如果仅仅使用 vector 会出现下面的结果：
[222,228,228,222,228,228,282,282,288,282,282,288,222,228,228,222,228,228,282,282,288,282,282,288,222,228,228,222,228,228,282,282,288,282,282,288,822,822,828,822,822,828,822,822,828,882,882,882,822,822,828,822,822,828,822,822,828,882,882,882]
其中有多个 228 ，这是因为分别使用 index=0 的 2 ，index=1 的 2 index=-1 的 2 全部被当成了不同的 2 ,然后组成了多个 228。
对于上面的问题可以使用 set 进行解决。
3.1.2 C++ 代码实现
3.1.3 时空复杂度
时间复杂度：O(n3+MlogM)
n 是 digit 的长度。M 是偶数的个数，对其进行排序。这里将偶数的处理放在最后，而不是放在最前面
空间复杂度：
O(M)：Set 的存储空间
LeetCode 题目链接
**带有返回值的回溯 **
3.2.1 算法描述
本题用到回溯是因为要判断从哪个字母开始，就如下面的字符串来说ABCCED 为什么要从第一个 A 开始，不从左下角的第一个 A 开始，所以这里用到回溯对每一个字母判断 " 是否从我开始 "
为什么要使用回溯，DP 不行
这里的函数使用 backtracking 作为递归函数，因为这里涉及左右括号所以要传入当前所判断的左右括号的个数，以及 n 的个数
2.递归的终止条件
当 path 中括号的个数到了 n*2 就可以终止了，并且将其保存在 res 中
3.单层递归逻辑
3.3.2 代码实现
3.3.3 时空复杂度
空间复杂度：O(n)
这里不需要判断
1.回溯算法参数
2.终止条件
左边括号的个数和右边括号的个数都不能大于 n
括号的总个数不能大于 2*n
总结：
1.组合问题
组合问题题目：在候选数组中找到所有满足某个条件的组合。如在 candidates = [10,1,2,7,6,1,5] 中找到 target = 8 的组合；输出
组合问题是从一堆数中选出有可能的组合，所以组合问题 path 和 path 是不能重复的，其次如果 candidates 中有重复的数
代表题目有：
77，216，39，40
应用题目：17 131 分割回文串 93 复原 IP 地址
2.子集问题
candidate 中如果有相同的值，path 中是否可以有相同的值出现
在递归 for 循环内如果 [4,6,7,7] 第一个 7 判断过了第二个 7 可以继续判断；所以可以出现结果 [4,7,7]
在同一轮 for 循环内第一个 7 判断过了，第二个 7 就不用再判断，所以不会出现结果 [7,7],[7,7]
分类：
candidate 中是否有重复：
starIndex 的值是多少,是否有 startIndex ，i 的值是 startIndex 还是 0
46（没有重复）
47（有重复）
Uesed 数组的作用，在 for 循环中如果 for 的初始化条件从 i=0 开始则递归过程中会有重复。用来判断 index 是否重复
set 数组的作用，在 candidate 无序时，没有办法使用 nums[i-1] ,nums[i] 是否是重复的。用来判断值是否重复