4-刷题记录

回溯算法

1. 回溯算法理论基础

   1. 回溯的本质是穷举，穷举所有可能，选出我们想要的答案。

   2. 可以解决的问题

      1. 组合问题：N个数按照一定规则找出k个数的集合。
      2. 切割问题：一个字符串按照一定规则有几种切割方式。
      3. 子集问题：一个N个数的集合里面有多少符合条件的子集。
      4. 排列问题：N个数按一定规则全排列，有几种排列方式。
      5. 棋盘问题：N皇后，解数独等。

   3. 回溯法解决的问题都可以抽象为树形结构。因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

   4. 回溯法模版：

      1. 回溯函数返回值及参数：返回值一般为void，先写逻辑，需要什么参数，就填什么参数。

         1	void backtracking(参数)

      2. 回溯函数终止条件：搜到叶子结点，也就找到了满足条件的一般答案，存放答案。

         1 2 3 4

         if (终止条件) { 存放结果; return; }

      3. 回溯函数的遍历过程：

         1 2 3 4 5

         for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 }

2. 组合问题

   1. 关键是确定好深度和宽度
   2. 确定好什么时候终结，保存结果

3. 组合总和III

   1. 关键是确定好深度和宽度
   2. 确定好什么时候终结，保存结果

4. 电话号码的字母组合

   1. 多绕了一圈，明白取出来的是什么
   2. 还需要注意引用的是对象，还是对象的副本

5. 组合总和

   1. 在除去重复顺序的解的同时，保证能够重复选用数组中的数字

6. 组合总和II

   1. candidates数组中有重复元素，导致解集中出现重复元素

      1 2 3 4

      if(i>idx && candidates[i]==candidates[i-1]) { continue; }

   2. 注意这个 i>idx，说明此时处于同一树层

7. 分割回文串

   1. 切割问题可以抽象成组合问题
   2. 如何模拟切割线
   3. 切割问题中递归如何终止
   4. 在递归循环中如何截取子串
      1. s.substring(int,int);
   5. 如何判断回文

8. 复合IP地址

   1. 判断子串是否合法
      1. 段位以0为开头的数字不合法
      2. 段位里有非正整数字符不合法
      3. 段位如果大于255不合法
   2. 用StringBuilder 操作字符串

9. 子集问题

   1. 注意处理空集的情况
   2. 注意，实时收集当前节点

10. 子集II

    1. 去重，同组合总和II思路
    2. 其余同子集问题

11. 非递减子序列

    1. 不能改变数组的原有顺序，所以去重逻辑不能使用之前的思路，可以构造一个数组，来表示是否使用过。

12. 全排列

    1. 顺序不同即不重复，需要考虑如何标记数组中使用过的元素和未使用过的元素
    2. 不可以再用startIndex，使用used数组。

13. 全排列II

    1. 加入去重逻辑
    2. 其余同全排列

14. 重新安排行程

    1. keypoints:
       1. 每张机票都必须用一次且只能用一次，也就是说，n张机票，n+1个行程
       2. 在一个行程中，处理航班时注意不能形成一个圈，称为死循环
          1. 不能重复使用，需要删去或者管理使用次数
       3. 存在多种解法，字母序靠前排在前面，需要记录映射关系
       4. 使用回溯法的终止条件是n张机票，n+1个行程，这个对应关系。
       5. 搜索的过程中，如何遍历一个机场所对应的所有机场
    2. 当不使用额外容器装载 || 使用额外容器装载、、–> 但是都会超时。
    3. 等刷到图相关的时候再解决这个题吧

15. N皇后

    1. 重点是检查是否合法
       1. 不能同行
       2. 不能同列
       3. 不能再一条斜线上（不只控制了相邻行，而是45度角线和135度线都不能同）

16. 解数独

    1. 先确定位置，再去看横向和纵向
    2. 什么时候return true ，什么时候回溯