一、簡述
回溯法，以窮舉的形式，對問題有可能出現(xiàn)的解羅列出來，必要的時(shí)候會(huì)包含剪枝的操作。根據(jù)羅列的形式不一樣，又有分為兩種：
子集樹 回溯
排列樹 回溯
二、步驟
- 根據(jù)題目，找到相應(yīng)解空間，即解可能的組合
- 選擇相應(yīng)的解空間樹（子集 or 排列），這一步最好畫出來，便于理解分析
- 使用深度優(yōu)先搜索（dfs）搜索樹（必要的時(shí)候帶上剪枝）
如上，因?yàn)榈?3 步可以直接套用 三、解題模型，因此重要的一步便是 2，選擇什么樣的結(jié)構(gòu)去解決題目，那么該如何確定選擇哪種結(jié)構(gòu)呢？如下分析：
子集樹：從給出集合中，找出滿足某些條件的子集。
如： 01 背包問題，就是從物品集合中，找出最大重量的子組合、排列樹：將集合中的元素，給出按照某些條件進(jìn)行排列的子集
如：排列數(shù)字，就是將集合（{1, 2, 3}）進(jìn)行排序，給出所有可能的排序。
三、解題模型
由于樹的搜索（這里是 dfs）可以選用棧或者遞歸的方式，因此也有兩種模型
1. 棧
pass，持續(xù)更新后補(bǔ)
2. 遞歸（常用）
使用遞歸的方式進(jìn)行通解，通常要定義如下參數(shù)：
- int k - 當(dāng)前層
- int n - 總層數(shù) （如果總層數(shù)使用解的個(gè)數(shù)，則無需定義）
- vector<T>& x - 解
- vector<T>& res - 記錄的結(jié)果
以及剪枝函數(shù)（有時(shí)候也叫限界函數(shù)）：
- constraint(k) 即判斷是否有必要進(jìn)行下一次的hui's
2.1 子集樹
void backtrack(int k, vector<T>& x, vector<T>& res) {
if (k >= x.size()) {
// 此處做記錄
res.push_back(x);
} else {
// 繼續(xù)深入
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 {
// 繼續(xù)深入
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) 方法對元素交叉排列，在結(jié)束之后再交換回來（恢復(fù)狀態(tài)）。
四、案例
TODO 持續(xù)更新
