回溯算法

1. 回溯算法

感谢代码随想录

1.1. 组合问题

1. 终止条件，满足题目条件

2. 处理逻辑

   1. 对当前所有可能结果遍历
   2. 调用函数
   3. 结果回溯，弹出函数修改的结果
   4. 在处理中，不合理的情况暂停，减枝

3. 函数参数选择

1.2. 组合问题2

组合问题

回溯算法： 宽度是for循环的数量，深度是满足条件回溯算法的深度

1. 终止条件：深度为K, 总和为n
2. 处理逻辑：
   1. 对于总和数< 1，没有结果，剪枝
3. 参数，可以函数调用时导入K-1, n-i，进行递归和回溯

1.3. 电话号码排列

排列问题

使用index 标识树的深度，或者其他方式也行

1. 终止条件：达到指定深度
2. 处理逻辑：
   1. 对字串中的所有char 进行遍历

1.4. 组合问题

组合中不同排序结果相同，使用startIndex标识开始位置，不同排序结果只记录一次

1.5. 组合总数

组合去重

数据中有重复数据，题目要求每个数据在每次只能用一遍，重复数据可以在同一结果集中出现，但是由于元素重复，需要对重复数据去重

去重条件candidates[i] == candidates[i-1] && used[i-1]==false，这一部分不是剪枝，必须去除这一部分

1.6. 切分回文子串

切分回文子串

1. 终止条件： 切分线到达最后，切分结束
2. 处理逻辑：
   1. 切分出来的是回文子串则继续切分，否则返回，不再切割
   2. 判断方法：
      1. 字串直接判断
      2. DP首先计算出DP数组，DP[i,j] 数组标识[i,j] 这范围内是否为回文子串， 回文子串dp[i][j] = s[i] == s[j] && dp[i+1][j-1]

1.7. 复原IP地址

复原Ip地址

1. 终止条件： 分割点数 == 3， 并且最后一个分割字串符合条件
2. 处理逻辑：
   1. 如果切分出来的是符合逻辑的IP, 继续切割
   2. 剪枝：
      1. 当剩余字符数s.size() - 1-(i+1)+1 = s.size()-i-1 超过所需字符数 3*(3- PointNum) ，剪枝
      2. 少于所需字符数（3-point) ,剪枝
3. 传递参数： 切割位置，切割的点数

1.8. 分割子集

搜集子集是将所有搜索路径上所有结果
组合和分割将叶子节点中符合条件的结果加入其中

如果题目要求集合中元素顺序，则下一个节点从i+1开始，如果当前节点可以重复使用从i开始；

节点中有重复元素，需要对重复元素去重，同一层中不能以当前节点继续，但是同一树仍可以继续使用

1.9. 子集去重

有重复元素，去重

1. 对数据集排序
2. 使用num[i]!=num[i-1] 对同层数据去重
3. 对于需要使用已加入栈中的数据时，需要使用used对数据去重

子集去重

组合去重

1.10. 递增子集去重

递增序列去重

递增序列中去重，当前序列中有重复元素，不能使用sort对数组排序。

使用set对当前层数组去重，每一个函数中创建一个set, 对函数中的当前层有效。同一树枝上因为从i+1开始，不用去重，且set已更新，不影响下一层数据

1. 处理逻辑：
   1. 符合条件的加入到path中

1.11. 排列问题

排列

1. 终止条件： 到达满足条件
2. 处理逻辑：
   1. 遍历对整个数组遍历，因为不同顺序集合不同，此时不需要startIndex;
   2. 使用used标识这条链路上哪个元素被使用， 将used作为参数；
3. 参数： 数组，标识数组used

1.12. 排列问题去重

因为排列问题需要从0开始，下一层中可能会使用到上一层的数据，需要使用used对检查是否在树枝，或同一层上；

判断条件：

1. nums[i] == nums[i-1] 并且 used[i-1] = false表示同一层中上一个被使用

   ​ 下一层中上一个被使用，used[i-1] =true, 可以被接着使用。

2. 同时，还需要使用used[i] 检查当前元素是否在树枝上使用过，使用过则跳过

3. 或者使用set代替第一条对数据去重

1.13. 重新安排路径

搜索机票

将票数据转换为图map<string, map<string, int>>

1. 终止条件： 节点数 = 机票数量+1
2. 处理逻辑：
   1. 对result最后一个节点的所有相连进行搜索
   2. 每搜索一次，删除一条机票，删除方式将第二个map数量-1，当= 0 时，不能从当前机票起飞

此题是欧拉路径，最好使用Hierholzer 算法，搜索算法可能进入贪心死循环

1.14. N皇后

N皇后

1. 终止条件： 加在最后一行棋盘
2. 处理逻辑：
   1. 对棋盘上每一行进行遍历
   2. 符合条件的加入棋盘
   3. 进入下一轮
   4. 回溯，退出上一轮的修改

1.15. 数独

37. 解数独 - 力扣（LeetCode）

1. 终止条件： 所有节点遍历结束，返回true;
2. 处理逻辑：
   1. 遍历宽度为1-9
   2. 遍历深度为所有节点遍历结束，因为是二维，不确定向那个方向移动，使用!='.'条件对已完成的跳过，实现对下一个移动方向的选择

详细代码注释如代码及注释