回溯

回溯是“做选择 → 递归深入 → 撤销选择”的搜索框架：走到某一步做出一个选择，沿着它往下搜；这条路探完后，一定要把选择撤销、恢复现场，再去试下一个选择。关键就在“恢复现场”。

以全排列为例：

int a[10];
bool used[10];
void dfs(int step) {
    if (step == n) { /* 输出一个排列 */ return; }
    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;
        used[i] = true; a[step] = i;   // 做选择
        dfs(step + 1);
        used[i] = false;               // 撤销选择, 恢复现场
    }
}

全排列共 $n!$ 种，复杂度 $O(n!\cdot n)$，所以 $n$ 一般很小（$\le 10$ 左右）。

坑：一是最容易漏写 used[i] = false 这行撤销，一漏就只能搜出一条路；二是“做选择”和“撤销选择”必须成对出现、前后对称；三是若用了全局的路径数组或计数器，回溯时也要一并还原，否则状态会串到别的分支。