构建、检查、撤销
[[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 和回溯，是同一个思想的三张脸：先深入，再回来。