一、简述
回溯法，以穷举的形式，对问题有可能出现的解罗列出来，必要的时候会包含剪枝的操作。根据罗列的形式不一样，又有分为两种：
子集树 回溯
排列树 回溯
二、步骤
- 根据题目，找到相应解空间，即解可能的组合
- 选择相应的解空间树（子集 or 排列），这一步最好画出来，便于理解分析
- 使用深度优先搜索（dfs）搜索树（必要的时候带上剪枝）
如上，因为第 3 步可以直接套用 三、解题模型，因此重要的一步便是 2，选择什么样的结构去解决题目，那么该如何确定选择哪种结构呢？如下分析：
子集树：从给出集合中，找出满足某些条件的子集。
如： 01 背包问题，就是从物品集合中，找出最大重量的子组合、排列树：将集合中的元素，给出按照某些条件进行排列的子集
如：排列数字，就是将集合（{1, 2, 3}）进行排序，给出所有可能的排序。
三、解题模型
由于树的搜索（这里是 dfs）可以选用栈或者递归的方式，因此也有两种模型
1. 栈
pass，持续更新后补
2. 递归（常用）
使用递归的方式进行通解，通常要定义如下参数：
- int k - 当前层
- int n - 总层数 （如果总层数使用解的个数，则无需定义）
- vector<T>& x - 解
- vector<T>& res - 记录的结果
以及剪枝函数（有时候也叫限界函数）：
- constraint(k) 即判断是否有必要进行下一次的hui's
2.1 子集树
void backtrack(int k, vector<T>& x, vector<T>& res) {
if (k >= x.size()) {
// 此处做记录
res.push_back(x);
} else {
// 继续深入
for (int i=0; i<=1; i++) {
x[t] = i; // 选 0 或者 1
if (constraint(k)) {
backtrack(k+1, x, res);
}
}
}
}
2.2 排列树
void backtrack(int k, vector<T>& x, vector<T>& res) {
if (k >= x.size()) {
// 此处做记录
res.push_back(x);
} else {
// 继续深入
for (int i=k; i<=x.size(); i++) {
swap(x[t], x[i]);
if (constraint(k)) {
backtrack(k+1, x, res);
swap(x[t], x[i]);
}
}
}
}
排列树主要是通过 swap(a: T, b: T) 方法对元素交叉排列，在结束之后再交换回来（恢复状态）。
四、案例
TODO 持续更新
