回溯算法part01
回溯算法
- 回溯算法的本质：本质是穷举，穷举所有可能，然后选出我们想要的答案
- 更高效的回溯算法：加入剪枝操作
- 回溯算法可以解决的问题类型
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
- 组合是不强调元素顺序的，排列是强调元素顺序。
- 理解回溯算法
- 回溯法解决的问题都可以抽象为树形结构
- 给定已知集合的大小就构成了树的宽度，递归的深度就构成了树的深度。
- 回溯模板
- 返回值以及参数：返回值一般为void，参数需要根据实际情况确定
- 终止条件
- 遍历过程：for(本层集合中的元素){处理；递归调用；回溯}
- for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历
- for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历
LC77组合
- 思路：使用回溯算法的思想和回溯算法的模板
- 终止条件，mid的size等于k
- for循环本层集合中的元素，即index到n
- 采用剪枝操作在每一层的for循环上进行优化
- 因为mid的size一定要满足k，当前for循环的情况下之后的结果数小于k的情况是一定不满足的可以直接舍弃
- 当前for循环已经有了mid.size()个结果，仍需要k-mid.size()个结果，因此i最大只能是n-[k-mid.size()]+1
- 暴力：了解暴力更容易理解为什么for循环从i=index开始，并且递归为i+1不会遗漏其他情况（每个元素只使用一次）
