23 · DFS 枚举：子集、组合与排列

换一种说法。一个排列就是把 1..n 各用一次，依次放进第 1、2、…、n 个格子。于是“输出所有排列”变成“枚举所有填法”，而填法可以一层一层决定：第 1 格填谁，第 2 格填谁……

状态记什么。只需要两样：已经填好的 a[1..step-1]，以及哪些数字已经被用掉。后者可以直接扫一遍 a 得到，但每次是 O(n)；用一个 vis[] 布尔数组把它压成 O(1)。这是“空间换时间”出现得最朴素的地方。

出口在哪。step 从 1 开始，填完第 n 格后进入第 n+1 层，此时 step > n，a[1..n] 就是一个完整排列，输出后 return。把出口写成 step == n 会漏掉最后一格，是本题第一大坑。

为什么不用排序就是字典序。每层循环 i 都从 1 到 n 递增。字典序比较的是“第一个不同的位置”，递归保证前面的位置先定下来、而且按从小到大尝试，于是输出的先后顺序就是字典序。

规模。节点数 = 1 + n + n(n−1) + … + n! ≈ e·n!，n = 9 时约 98.6 万个节点、362880 个叶子。每个叶子输出 9 个数 × 5 字符 ≈ 46 字节，总输出约 16 MB——本题的瓶颈是输出，不是搜索。

把子集、组合、排列写成同一副骨头，差别只在循环怎么写。这三段建议直接背下来，之后所有搜索题都是往里面填东西。

#include <bits/stdc++.h>
using namespace std;

int n = 3, a[25], top = 0;

void dfs(int i) {
    if (i > n) {                          // 每个元素的去留都定了
        for (int k = 1; k <= top; ++k) cout << a[k] << ' ';
        cout << '\n';
        return;
    }
    dfs(i + 1);                           // 分支一：不选 i
    a[++top] = i;                         // 分支二：选 i，先占位
    dfs(i + 1);                           //        再往下
    --top;                                //        回来时弹出（这就是还原）
}

int main() { dfs(1); }                    // 2^3 = 8 行，第一行是空集

#include <bits/stdc++.h>
using namespace std;

int n = 5, k = 3, a[25];

void dfs(int step, int start) {
    if (step > k) {
        for (int i = 1; i <= k; ++i) cout << a[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = start; i <= n; ++i) {    // 起点是 start，不是 1
        a[step] = i;
        dfs(step + 1, i + 1);             // 下一层起点右移一格
    }
}

int main() { dfs(1, 1); }                 // C(5,3) = 10 行

③ 排列就是例题：候选集是“1..n 中所有没被用过的数”，用 vis 判重。三者对照一下：子集的分支数固定为 2，不需要循环；组合的循环起点是变的；排列的循环起点固定、靠 vis 排除。

还有一条容易忽略：子集模板里 --top 就是“回溯三行”的第三行，只不过这里占位的是一个栈指针而不是 vis。还原的对象永远是“你刚才改动的那份状态”，把它找出来，回溯就不会写错。