总论
- 增量构造答案
- 关注边界条件的逻辑
- 当前操作？（选/不选，枚举选哪一个）
- 子问题？
- 下一个子问题？
- 用什么数据结构保存搜索路径？
- 时间复杂度计算：搜索树节点数*生成答案需要的时间
题目分类
可以分成子集型、排列型和组合型三种：
| 回溯问题 | 时间复杂度O() | 解法 |
|---|---|---|
| 子集 LC78 | n x 2^n | 记录下标i+1 |
| 子集 II(有重复) LC90 | n x 2^n | 同上+hash |
| 排列 面试题08.07 | n x n! | Vis数组管理或者swap下标 |
| 排列II(有重复) 面试题08.08 | n x n! | 同上+hash |
| 组合型 括号生成LC22 | C(2n,n) | 剪枝+叶子节点push |
- 使用hash可以理解为一种剪枝方式，主要是去掉重复元素
- 组合型需要对普通回溯结果根据预设条件进行剪枝
子集型
从执行和答案两个角度考虑问题：
- 选与不选是从叶子节点的角度考虑，在叶子节点再push答案
- 枚举选哪个是从回溯过程的角度考虑，需要考虑下标管理，从更大的下标中构造子集
注意使用位运算的迭代思路：不回溯，直接使用2^n位运算计算出上限，然后for循环变量作为mask依次处理
组合型
- 从n个数字中选择k个数的组合，可以认为是寻找路径长度固定为k的子集
- 有额外剪枝的可能性，因为选择有顺序(组合保证了顺序的存在，顺序起到了去重的效果)
- 组合: 每次选的范围缩小，都在0, i-1内，人为规定的逆序
- 括号生成：状态改变时候的性质
- 时间复杂度=路径长度X叶子个数，即k X C(n, k)
排列型
可以重复，但顺序不同，因此需要有一个结构存储接下来还能保存哪些数：
- path：记录搜索路径
- 集合s：hash记录未选的数字/布尔数组
全排列O(n*n!): 节点路径长度x叶子节点个数
注意全排列可以使用交换法实现，比较巧妙的处理
参考
- https://www.bilibili.com/video/BV1xG4y1F7nC/?vd_source=c80c62eac86a4ba033ab112349bbdd9f
- https://www.bilibili.com/video/BV1mG4y1A7Gu/?vd_source=c80c62eac86a4ba033ab112349bbdd9f&spm_id_from=333.788.videopod.sections
- https://leetcode.cn/problems/permutation-i-lcci/solutions/406850/quan-pai-lie-jiao-huan-fa-qing-xi-tu-shi-by-chen-k/?envType=problem-list-v2&envId=xb9lfcwi