三步走解决回溯问题
开启新的刷题章节，之前学习了三步走套路递归问题，在二叉树的章节得到了广泛的应用。这里继续学习一种新的搜索方法，回溯搜索。
1. 回溯的定义和适用场景
1.1 回溯的定义
-
回溯指的是对当前的节点对象处理后，返回连接的上一个父节点的对象，继续进行处理。本质上，回溯是递归的副产品，只要存在有递归就一定有回溯。所以总得来说，回溯函数就是递归函数，指的都是一个函数，只是回溯用的方法更为复杂。
-
回溯的使用效率并不是很高，本质上还是利用的是嵌套的穷举方法，如果此时嵌套的层数较少的时候，用for循环可能会更为直接。但是，和直接穷举的for循环不同的是。回溯可以实现剪枝，对不需要搜索的分支进行剔除。但总得来说，依然是暴力搜索的方法，穷举的话效率较低，优点是比较通用省事~
1.2 回溯的适用场景
-
回溯法一般解决以下的几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
-
组合是不强调元素顺序的，排列是强调元素顺序。
- 例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。
- 记住组合无序，排列有序，就可以了。
-
除此之外，刚才说明了回溯法本质的回溯函数其实就是递归函数，所以所有可解决的类型都可以抽象到树形结构当中去。回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。
-
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
2. 三步走模板解决
- 类似于递归函数的模板，回溯的模板也分为三步：
回溯模板的返回值以及参数
- 函数的名称随意，返回值一般是void
- 参数：因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
void backtracking(参数)
回溯函数终止条件
- 树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
if (终止条件) { 存放结果; return; }
回溯搜索的遍历过程
这里给出代码随想录的一张图片：
回溯的伪代码：
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 }
- for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历
-
由上述得到一个框架：
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }
3. 举例实战
-
这里我相对上述适用的问题一一解答，但是考虑到篇幅的原因，就分析了组合问题吧，后续有兴趣回来再补充几道其他类型的题目：
-
3.1 题目说明
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]提示：
-
1 <= n <= 20 -
1 <= k <= n
3.2 模板分析
-
递归函数的返回值和参数
-
在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
-
函数里一定有两个参数，既然是集合n里面取k个数，那么n和k是两个int型的参数。
-
然后还需要一个参数，为int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,…,n] ）。
-
-
简单地说，为了避免重复遍历的情况，我们只对未遍历的节点进行判断，比如输入了{1，2}判断后，到2节点的时候就不再对{2，1}判断了，而是对后续的节点{3，4，…}进行条件判断了~，如下图所示：
-
回溯函数终止条件
- 到达叶子节点后，path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。
- 此时利用result二维数组/列表进行记录保存，结束本层的递归
-
回溯搜索的遍历过程
-
for循环横向遍历，递归纵向遍历
-
for循环每次从startIndex开始遍历，然后用path保存取到的节点i。
-
3.3 具体代码
class Solution {
List<List<Integer>> result= new ArrayList<>(); // 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>(); // 用来存放符合条件单一结果
public List<List<Integer>> combine(int n, int k) {
backtracking(n,k,1); //注意题义指的是[1,n]的组合，当然从1开始递归遍历
return result;
}
public void backtracking(int n,int k,int startIndex){
if (path.size() == k){
result.add(new ArrayList<>(path));
return;
}
for (int i =startIndex;i<=n;i++){ // 控制树的横向遍历
path.add(i); // 处理节点
backtracking(n,k,i+1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
path.removeLast(); // 回溯，撤销处理的节点
}
}
}-
复杂度分析：
-
时间复杂度：
-
其中n表示数字范围的大小，k表示组合的长度。
-
在backtracking方法中，我们使用递归来生成所有可能的组合，每次选择一个数字加入当前组合，然后递归生成下一个位置的数字，最后再将该数字从当前组合中移除。
-
因此，每个数字都有两种可能：被选择或不被选择。总共有C(n, k)个不同的组合，其中C(n, k)表示从n个数字中选择k个数字的组合数。所以时间复杂度是O(C(n, k))。
-
-
空间复杂度：
- 其中n表示数字范围的大小，k表示组合的长度。
- 在backtracking方法中，我们使用了一个LinkedList来存储当前的组合path，而result则用来存储最终的结果。在递归的过程中，path的大小最大为k，因此占用的空间为O(k)。
- 而result中最多会存储C(n, k)个组合，所以占用的空间为O(C(n, k))。因此，总的空间复杂度为O(k * C(n, k))。
-
3.4 剪枝优化
-
由于设置了startindex，每次对当前层级的for循环遍历的话，只有可能在满足长度为k的基础上进行深度下查。比如：
n=4,k=4;
对于第一层的2节点而言，其startindex后的数组只含有[3,4]，不满足长度为k=4的子数组了，所以可以直接剪枝~
-
所以就是对for循环每层的遍历顺序进行操作：
-
已经选择的元素个数：path.size();
-
还需要的元素个数为: k - path.size();
-
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
-
为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
-
举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。从2开始搜索都是合理的，可以是组合[2, 3, 4]。
-
-
优化后的for循环代码处：
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置
周末过得蛮充实的，下周要继续努力啦✊
加油😀
