做一个选择，递归下去；行不通（或者已经记录完）就撤销这个选择，换下一个再试。
12.1 节走迷宫的例子里提到过：一个格子的四个方向都试过、都走不通之后，函数自然 return 回到上一层——这个"退回上一层"的过程叫回溯，但当时的代码里没有任何一行显式写着"撤销"，因为迷宫本身没有需要撤销的东西（走过的格子还是走过了，visited 也没必要重新变回 false）。
但很多问题不是"找一条能走通的路"，而是要构造出一个完整的方案——比如"列出所有排列方式""从几个物品里选出一部分组合"。这类问题在递归过程中会维护一个"当前正在构造的方案"，每往下递归一层，就往这个方案里加一个新的选择；一旦这一层的某个分支处理完了，要退回上一层去尝试别的选择时，就必须把刚才加进方案里的这个选择拿掉——不拿掉的话，方案会一直越攒越多，后面的分支会带着不属于自己的"脏数据"。这个"拿掉刚才加的选择"的动作，就是本节要讲的回溯，和 12.1 节比，"撤销"这一步终于要显式地写进代码里了。
用最经典的例子来看：把 [1, 2, 3] 这三个数排成一排，有多少种不同的排法？回溯的思路是——维护一个"当前已经排好的部分" path，每次从"还没用过的数"里选一个加进 path，递归下去；如果 path 已经排满了（三个数都用上了），就记录下这一种排法；不管有没有记录，处理完之后都要把刚才加进去的数从 path 里移出去，这样才能换下一个数继续试。
path 每次只增加或减少最后一个元素，增加发生在递归调用之前，减少（撤销）发生在递归调用之后——这一"先加后减"的顺序，保证了 path 在整个过程中，任何时刻都精确对应"从根节点走到当前这一层"所做过的选择。把所有分支都走一遍，会得到一棵完整的决策树——每个分支走到底（path 排满 3 个数）就是一种排列，一共有 3 × 2 × 1 = 6 种：
path 的内容，粉色 ✓ 是记录下一种排列，橙色是"撤销选择"。六条分支互不干扰——每次撤销之后，path 都准确地回到了"进入这一层之前"的状态，所以从同一个节点出发的不同分支，看到的都是干净的、没有被别的分支"污染"过的 path。| 1 | #include <iostream> |
| 2 | using namespace std; |
| 3 | |
| 4 | int nums[] = {1, 2, 3}; // 要排列的这几个数 |
| 5 | int path[3]; // 当前正在构造的排列 |
| 6 | bool used[3]; // used[i] 表示 nums[i] 是否已经用在 path 里了 |
| 7 | |
| 8 | void Backtrack(int depth) // depth：path 里已经填了几个数 |
| 9 | { |
| 10 | if (depth == 3) // path 排满了，是一种完整的排列 |
| 11 | { |
| 12 | for (int i = 0; i < 3; i++) { cout << path[i] << " "; } |
| 13 | cout << endl; |
| 14 | return; // 记录完就返回，这一层不用再往下走了 |
| 15 | } |
| 16 | |
| 17 | for (int i = 0; i < 3; i++) // 依次尝试把 nums[i] 作为下一个数 |
| 18 | { |
| 19 | if (used[i]) { continue; } // 这个数已经用过了，跳过 |
| 20 | |
| 21 | path[depth] = nums[i]; // ① 做选择：把 nums[i] 放进 path |
| 22 | used[i] = true; |
| 23 | Backtrack(depth + 1); // ② 递归下去，填 path 的下一个位置 |
| 24 | used[i] = false; // ③ 撤销选择：把 nums[i] 标记回"未使用" |
| 25 | } |
| 26 | } |
| 27 | |
| 28 | // 调用方式：Backtrack(0); |
path[depth] 不需要显式"清空"？因为下一次这个位置被用到时，一定会先执行第 21 行的赋值，把旧值直接覆盖掉——不会有代码去读一个"应该被撤销但没清空"的 path[depth]。真正必须撤销的是第 24 行的 used[i] = false，因为 used 数组是靠"读取"来判断某个数能不能选的，如果不撤销，这个数在其它分支里会一直被误判为"已经用过"，导致某些排列永远生成不出来。把本节内容汇总成几条最容易踩坑的规则：
used[i] = false 这一行，某个数一旦被用过，就会在所有其它分支里都被当成"已使用"，永远不会再被选中——最终只能生成一部分排列，而且通常是错误地"漏掉"了很多种，而不是报错崩溃，非常隐蔽。path、标记 used），第 24 行撤销时必须把对应的每一件事都撤销一遍。如果做选择时改了三个状态、撤销时只改了两个，等于留下了"半撤销"的脏状态，后面的分支会读到不该存在的数据。vector 存 path，撤销要用 pop_back()，不能用"覆盖下一个值"来偷懒：本节用固定长度的数组 path[3]，覆盖赋值确实够用；但如果改用 vector<int> path 并且用 push_back 做选择，撤销那一步必须显式调用 path.pop_back() 删掉最后一个元素，否则 path 的长度会只增不减，第 10 行判断"排满了没有"的条件也会跟着出错。