递归 = 决策树：子集、组合、全排列

第 1 章讲的是「怎么相信一个还没写完的函数」。这一章讲的是递归真正的主场： 当你需要把所有可能性一个不漏地枚举出来的时候。

这是信息学竞赛里出现频率最高的场景之一。搞定它，DFS、回溯、剪枝、状压全都有了地基。

1 一句话问题

给 n 个正整数，从中选出若干个（可以一个都不选），问有多少种选法使它们的和恰好等于 m。

输入      3 5           n=3 个数，目标和 m=5
          3 5 2
输出      2             因为 {5} 和 {3,2} 两种选法的和都是 5

2 先用纸笔手算一遍

n = 3 只有 8 种选法，全列出来（√ 表示选）：

答案是 2。请注意这张表的行数：8 = 2³。每个数都有「选」和「不选」两种可能， n 个数就是 2ⁿ 种组合。这个 2ⁿ 后面会反复出现。

3 第一种写法：二进制枚举

看着上面那张表，很容易发现每一行就是三个 0/1 —— 正好是一个三位二进制数。 于是枚举 0 到 2³-1，用位运算取出每一位：

点「运行 ▶」看结果

这个写法很聪明，也很短。但它有个天花板，第 5 步就会撞上。

4 先确认它是对的

跑一下上面的样例，应该输出 2。再试试这几组：

1 0          答案 1（一个都不选，和是 0）
5

4 10         答案 2（{1,2,3,4} 和 {4,6}）
1 2 3 4

确认无误。它将成为我们的标准答案。

5 二进制枚举的天花板在哪

它把「一连串决策」压扁成了一个整数。压扁之后，中间过程就消失了。

具体来说，下面这三件事它都做不了：

1. 剪枝。如果选到第 3 个数时和已经超过 m 了，后面的数怎么选都没用， 本该立刻掐掉这一整片分支。但 mask 是一次性生成的，你没有「选到一半」这个时刻。
2. 排列。如果「先选 3 再选 5」和「先选 5 再选 3」算两种不同方案， 一个 0/1 掩码根本表达不了顺序。
3. n > 63。1 << n 会溢出，写不了。

第 1 条尤其致命。搜索题的分数几乎全靠剪枝，而剪枝的前提是你必须能站在决策过程的中间。

6 ★ 关键的一步

                        dfs(i=0, sum=0)
                 不选 ┌────────┴────────┐ 选 a[0]=3
            dfs(1, 0)                   dfs(1, 3)
            ┌────┴────┐                 ┌────┴────┐
       dfs(2,0)   dfs(2,5)         dfs(2,3)   dfs(2,8)
         ┌─┴─┐      ┌─┴─┐            ┌─┴─┐      ┌─┴─┐
         0   2      5★  7            3   5★     8  10

翻译成代码，只有两行：

void dfs(int i, long long sum) {
    if (i == n) { if (sum == m) count_++; return; }   // 到叶子了
    dfs(i + 1, sum);            // 左边这一叉：不选 a[i]
    dfs(i + 1, sum + a[i]);     // 右边这一叉：选 a[i]
}

dfs(i, sum) 的职责（还记得第 1 章的三要素吗）： 前 i 个数已经决策完了，当前和是 sum，负责数清剩下的 a[i..n-1] 有多少种选法能凑到 m。

7 递归写法

点「运行 ▶」看结果

8 把整棵决策树打印出来

点「运行 ▶」看结果

注意 trace.cpp 里这一对操作：

chosen.push_back(a[i]);        // 进入「选」这个分支前：记下选择
dfs(i + 1, sum + a[i], "选");
chosen.pop_back();             // 从分支回来后：撤销选择

这就是回溯。现在它只是为了打印好看，但到了全排列、N 皇后，它是算法本身不可缺的一步。 记住这个「进入 → 递归 → 撤销」的三段式，第 4 章会把它变成肌肉记忆。

9 单步看决策树长出来

播放一遍，盯住这几件事：

• 它总是先一头扎到最左边的叶子，才回头处理第二个叶子 —— 这就是「深度优先」。
• 蓝色高亮的那条路径 = 此刻的递归栈，和第 1 章调用栈动画里的那根柱子是同一个东西。
• 走到叶子时才判断 sum == m，命中的叶子变绿打星。
• 试着把「数字」改成 4 个（比如 3 5 2 4），看叶子数从 8 变成 16 —— 每加一个数就翻倍。

10 ★ 对拍验证

常见错误，故意写一个试试：

• dfs(i + 1, sum + a[i]) 写成 dfs(i, sum + a[i])（i 忘了 +1）→ 死循环
• 出口写成 if (i == n - 1) → 最后一个数没被决策到
• 两个分支写成 dfs(i+1, sum); dfs(i+1, sum); → 永远算不到「选」的情况

11 第二个例子：全排列 —— 循环真正的天花板

上面的子集和，二进制枚举勉强还能顶。但全排列不行，这里能看到循环彻底失效的地方。

输出 1..n 的所有排列。n = 3 时用三重循环还写得出来：

点「运行 ▶」看结果

把输入改成 4 再跑一次 —— 它做不了。

点「运行 ▶」看结果

注意这里的回溯：

used[v] = true;      // 占用数字 v
perm[pos] = v;
dfs(pos + 1);
used[v] = false;     // 释放（必须！）

used[v] = false 忘了写，是初学回溯的头号错误 —— 结果是只能输出一条排列就没了。 去掉那一行跑一次，亲眼看看会发生什么，比记住这句话有用。

12 自测