回溯算法--总结1

第一周总结

1. 回溯问题抽象为树形结构，可以直观的看出其搜索的过程：for循环横向遍历，递归纵向遍历，回溯不断调整结果集。
2. 回溯算法三部曲：
   1. 参数。
   2. 终止条件。
   3. 单层递归逻辑。
3. 剪枝：
   1. 剪枝1：for循环在寻找起点的时候要有一个范围，如果这个起点到集合终止之间的元素已经不够 题目要求的k个元素了，就没有必要搜索了。
   2. 剪枝2：在求和问题中，排序之后加剪枝是常见的套路！
   3. 比如组合中要求有四个元素，从1-9中选择，当遍历到6时就没必要继续递归了。因为往后不够四个元素。
4. startIndex：
   1. 一般只有一个集合求组合问题时候，使用startIndex，并且能保证组合中的元素不重复。
   2. 有多个集合从中求组合问题时，不需要使用startIndx，比如电话号码的字母组合。
   3. 注意以上说的是求组合的情况，如果是排列问题，又是另一套分析的套路，后面我在讲解排列的时候会重点介绍

第二周总结

1. “树枝去重”和“树层去重”。
   1. 在candidates[i] == candidates[i - 1]相同的情况下：
      • used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
      • used[i - 1] == false，说明同一树层candidates[i - 1]使用过
2. 切割问题（分割回文串）
   1. 切割问题其实类似组合问题
   2. 如何模拟那些切割线：startIndex模拟切割线
   3. 切割问题中递归如何终止
   4. 在递归循环中如何截取子串
3. 子集问题
   1. 在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果。