構建、檢查、撤銷
[[backtracking|回溯]]是一種有結構地探遍一個問題所有可能性的辦法，它通過增量地構建解來進行。每一步你做一個試探性的選擇，遞迴下去把它延展，如果那條路走到死胡同，你就撤銷這個選擇、再試另一個。想像用一團線走迷宮：你往前走，一旦撞牆，就把線收回到上一個岔路口，換個方向再拐。
回溯本質上是在一棵決策樹上做深度優先搜索，由遞迴驅動。樹的每個節點是一個部分解；每條分支是一個可能的下一步選擇；每片葉子是一個完整的候選解。那個`撤銷`步驟——把狀態還原到做選擇之前的樣子——正是它讓一個函式能探遍整棵樹而不在身後留下爛攤子。
實例：所有排列
我們來生成 `[1, 2, 3]` 的每一種排列。在遞迴的每一層，我們挑一個還沒用過的數，把它標記為已用，遞迴去填剩下的，然後再取消標記。這個標記與取消標記，*就是*那對選擇/撤銷。
[ ] <- nothing chosen yet
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3][1,3,2] [2,1,3][2,3,1] [3,1,2][3,2,1] <- 6 leaves = 3! perms#include <vector>
void permute(std::vector<int>& nums, std::vector<bool>& used,
std::vector<int>& path, std::vector<std::vector<int>>& out) {
if (path.size() == nums.size()) { out.push_back(path); return; } // leaf
for (int i = 0; i < (int)nums.size(); i++) {
if (used[i]) continue; // skip already-chosen numbers
used[i] = true; path.push_back(nums[i]); // CHOOSE
permute(nums, used, path, out); // EXPLORE
path.pop_back(); used[i] = false; // UN-CHOOSE
}
}子集，與剪枝的威力
子集還要更簡單：對每個元素，唯一的決定就是*要還是不要。*那是一棵深度為 `n` 的二元選擇樹，給出 2^n 個子集。回溯這樣走它：把一個元素納入（選擇）、遞迴、再把它排除（撤銷）。但回溯之所以真正勝過暴力，靠的是剪枝：一旦一個部分解被證明毫無希望，你就停下回退——一刀砍掉整棵浪費功夫的子樹。
N 皇后是個招牌例子。在一個 `n×n` 的棋盤上放 `n` 個皇后，使得彼此都不能攻擊。樸素的擺法數目大得嚇人，但回溯一次放一行皇后，並在一個新皇后與已放的某個共列或同對角線時*立即剪枝*。這一個檢查，在那龐大的樹還沒被探索之前，就把它的絕大部分扔掉了——把一個不可能的搜索變成了一個可處理的搜索。
通用模板
幾乎每一個回溯解都套同一個形狀。一旦你寫過幾遍，新題就變成了填空：什麼算一個完整解，有哪些可選的選擇，以及是什麼讓一個選擇無效（這樣你才能剪枝）。
- 如果部分解已經完整，把它記錄下來並返回（你到了一片葉子）。
- 遍歷下一個位置上可用的選擇。
- 剪枝：如果一個選擇明顯無效，現在就跳過它——連遞迴都不要。
- 選擇：把這個選擇應用到部分解上。
- 探索：遞迴去延展它。
- 撤銷選擇：在試下一個之前撤銷這個選擇。
如果這個模板讓你覺得眼熟，那太好了——它正是你在遍歷樹和圖時見過的那同一種深度優先下降，只不過現在用在一棵*決策*之樹、而非*資料*之樹上。遞迴、DFS 和回溯，是同一個思想的三張臉：先深入，再回來。