回溯模板
关于构造回溯抽象树
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }
for循环中嵌套递归，这就是回溯的基本格式，最重要的就是将其抽象为一颗树，固定一个根节点，就拿leetcode46全排列来说
// 全排列核心代码 void backtracking(vector<int> nums, vector<bool> used){ if (path.size() == nums.size()) { result.push_back(path); return; } for (int i = 0; i < nums.size(); i++) { if (used[i] == true) continue; used[i] = true; path.push_back(nums[i]); // 加入path数组 backtracking(nums, used); path.pop_back(); used[i] = false; } }
- 假设输入样例是
[1, 2, 3]，那么根节点就是[1, 2, 3]，也就是nums数组，回溯操作就是在其中取值加入另一设好的path集合，将其作为节点，令节点的内容就是path组合的内容，没有进入递归的最外层的for循环成为外层for循环，假设只看外层for循环不管递归部分则有下图
可以察觉到的是，只关注外层for循环的话就发现他遍历了树的宽度，我们可以猜测，递归则就是遍历数的深度，接下来我将对当最外层for循环i=0时的操作细画图
其余两个节点的详细图类似
这个图的对应代码为
void backtracking(vector<int> nums, vector<bool> used){ if (path.size() == nums.size()) { result.push_back(path); return; } for (int i = 0; i < nums.size(); i++) { path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); } }
这就是最原始的回溯，在for循环内部没有任何筛选条件，所有回溯的题目都是在此基础上加条件进行节点的删除，全排列这道题就是加了used数组，目的在于去除同一路径下的相同位置的节点，删除的节点如下图所示
那许多组合相关的题目中的startIndex参数是拿来干什么的呢，其实也是删除一些节点，他就是令每个父节点下遍历子节点时index索引不重启，如下图所示
可以看出从上随着深度的增加i的值只增不减，这就是startIndex的作用，由于大量节点被删除，因此画出整棵树
可以直观的感受到startIndex的作用，利用伪代码表示startIndex
void backtracking(vector<int> nums, int startIndex){ // ... 终止条件 for(int i = startIndex; i < nums.size(); i++){ // ... backtracking(nums, startIndex + 1); // 对应回溯操作 } }
一些题目举例
各种去重条件
- 全排列1
- 去掉同一树枝下的相同结点
- 全局的集合查找
- 全局的
bool数组标记
- 全排列2
- 去掉同一树枝下的相同结点
- 只能用全局的
bool数组标记
- 去掉同一层下的相同结点
- 局部的集合查找
- 。。。以后再来加
