回溯算法理论基础
1.什么是回溯？
回溯法，也称回溯搜索法。是一种搜索方式。
递归和回溯是同时存在，递归进入对应回溯返回。
2.回溯法的本质
本质是穷举，穷举所有可能，然后选出需要的答案。
是一种暴力解法，可以剪枝操作。
3.解决的问题
一般解决如下几种问题：
①组合问题：N个数里面按一定规则找出k个数的集合
②切割问题：一个字符串按一定规则有几种切割方式
③子集问题：一个N个数的集合里有多少符合条件的子集
④排列问题：N个数按一定规则全排列，有几种排列方式
⑤棋盘问题：N皇后，解数独
【共性】：一定规则的约束，多个数字或字符串在该规则下有多种结果。
4.怎么理解回溯法
回溯法解决的问题都可以抽象为树形结构
回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成了树的深度。
5.回溯法模板
由递归三部曲，得到回溯三部曲
1.回溯函数返回值及参数
函数返回值一般为void
回溯函数的参数不容易一次确定，一般先写逻辑，然后需要什么参数，就填什么参数…
1// 回溯函数返回值及参数 2void backtracking(参数) 3
2.回溯函数终止条件
一般遍历到叶子节点或者找到了满足条件的答案，把这个答案存起来，并结束本层递归
1// 回溯函数终止条件 2void backtracking(参数) 3
3.回溯函数的遍历过程
回溯法一般在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成了树的深度.
1// 回溯函数的遍历过程 2for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 3 处理节点; 4 backtracking(路径，选择列表); // 递归 5 回溯，撤销处理结果 6}
for循环是横向遍历，backtracking(递归)是纵向遍历
回溯算法模板：
1void backtracking(参数) { 2 if (终止条件) { 3 存放结果; 4 return; 5 } 6 7 for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 8 处理节点; 9 backtracking(路径，选择列表); // 递归 10 回溯，撤销处理结果 11 } 12}
LeectCode: 77. 组合
1. 思路
明确结果：获取单个结果，将结果添加到结果集中
遍历方式：for循环进行横向遍历，在横向遍历的基础上递归函数进行深度遍历，防止有重复的结果
在深度遍历时，需要记录要遍历的深度位置用startIndex标识实现
当结果长度和k相同时终止，将结果添加到结果集中即可
2.代码实现
1class Solution { 2 List<List<Integer>> result = new ArrayList<>(); // 存放最终结果集 3 LinkedList<Integer> path = new LinkedList<>(); // 存放每条路径的结果 4 5 public List<List<Integer>> combine(int n, int k) { 6 combineHelper(n, k, 1); 7 return result; 8 } 9 // 确定回溯函数递归逻辑 10 private void combineHelper(int n, int k, int startIndex) { 11 // 确定终止条件：当path中的个数等于k时加入到结果集result中 12 if (path.size() == k) { 13 result.add(new ArrayList<>(path)); 14 return; 15 } 16 // for循环进行横向遍历 17 for (int i = startIndex; i < n - (k - path.size()) + 1; i++) { 18 path.add(i); 19 // 递归进行深度遍历 20 combineHelper(n, k, i + 1); // i + 1 代表表示递归遍历的层数 21 path.removeLast(); 22 } 23 } 24}
3.复杂度分析
时间复杂度：函数调用的次数和for循环次数决定，一次递归结果包含函数调用1次和for循环1次，共2次，记为则为2^1，k次递归，则为2^k.n个数，则复杂度为O(n*2^k).
空间复杂度：递归函数消耗栈空间，定义结果集消耗堆空间。则复杂度为O(n+m)
