同一个问题「从 $1 \sim n$ 里选 $m$ 个数」，有两种最常见的递归写法：

  • 二叉树递归版：每个数字二选一（选 / 不选），按数字分层
  • for 多叉版：每层填一个位置，按已选个数分层

两种都是 DFS、都是前序，但遍历的搜索树根本不是同一棵。

一、问题

从 $1 \sim n$ 中选出 $m$ 个数，按字典序输出所有组合。

以 $n = 3,\ m = 2$ 为例，答案只有三组：

1
{1,2}  {1,3}  {2,3}

二、写法 A：二叉树递归（选 / 不选）

2.1 核心思想

每一层对应一个数字，每个节点只有两个分支：拿它，或者不拿它。

1
2
3
4
5
6
7
8
9
10
11
12
13
int n, m;
vector<int> a;

void calc(int x) {                    // 正在决定数字 x 选不选
    if ((int)a.size() + (n - x + 1) < m) return;  // 剪枝：后面的全选也凑不满
    if ((int)a.size() == m) { prt(); return; }    // 已经选够 m 个，输出
    if (x > n) return;                            // 数字用完了

    a.push_back(x);
    calc(x + 1);                      // 分支 1：选 x
    a.pop_back();                     // 回溯：撤销选择
    calc(x + 1);                      // 分支 2：不选 x
}

调用入口：calc(1)。

分支顺序决定输出顺序：先走「选」得到字典序 {1,2} {1,3} {2,3}；先走「不选」会得到逆字典序 {2,3} {1,3} {1,2}。两者答案集合一样，但多数题目要求字典序，所以先写「选」。

2.2 搜索树长什么样

$n=3,\ m=2$，树高 = 3，每一层是一个数字（下图就是代码实际展开的节点，含 a.size() == m 的提前返回）：

另外还有剪枝 a.size() + (n - x + 1) < m：剩下的数字全选也凑不满时，整棵子树直接砍掉，所以上面这棵树实际只会展开一小部分。

三个绿色叶子就是答案，并且是按字典序出现的：

选择路径 结果
选1，选2（已满 m 个，直接输出） {1,2}
选1，不选2，选3 {1,3}
不选1，选2，选3 {2,3}

2.3 特点

  • 树高固定为 $n$，一个数字一层
  • 每个节点永远是 2 个分支，是一棵二叉树
  • 剪枝很好写：剩余可选数量 + 已选数量 < m 直接砍掉
  • 适合「每个元素独立做决定」的子集类问题（01 背包的暴力、选不选某点等）

三、写法 B：for 多叉版（按位置分层）

3.1 核心思想

每一层对应「答案里的第几个位置」，节点决定这一位放谁。

1
2
3
4
5
6
7
8
9
10
11
12
int n, m;
vector<int> a;

void calc(int pos, int start) {       // 正在填第 pos 位，只能从 start 开始挑
    if (pos == m) { prt(); return; }  // 填够 m 位，输出

    for (int i = start; i <= n; i++) {
        a.push_back(i);               // 这一位放 i
        calc(pos + 1, i + 1);         // 下一位只能从 i+1 开始，保证不重复、不倒退
        a.pop_back();                 // 回溯
    }
}

调用入口：calc(0, 1)。

start 参数是去重的关键：它保证下一个位置只在当前数之后取，生成的组合天然有序、不重复。

3.2 搜索树长什么样

$n=3,\ m=2$，树高 = 2，每一层是答案里的一个位置：

pos == m 时直接输出，不再往下展开，所以叶子节点就是答案。

输出顺序就是 {1,2}、{1,3}、{2,3}，天然字典序，不用额外排序。

3.3 特点

  • 树高固定为 $m$，一个位置一层
  • 每个节点的子节点数量不固定，是一棵多叉树
  • 逻辑直接对应「凑够 $m$ 个就输出」
  • 适合「定长组合」类问题；排列的话把 start = i + 1 换成 start = 1 再加一个 used[] 即可

四、两者的共同点

  1. 都是 DFS：一路往深处走到底，再退回上一层换分支
  2. 都是前序遍历：先处理当前节点（把数字塞进数组），再递归往下；递归全返回后才撤销（回溯）
  3. 都靠回溯复原现场：push_back 和 pop_back 必须成对出现
  4. 输出顺序都由「枚举顺序」决定：for 版 i 从 start 递增，天然字典序；二叉版把「选」分支写在前面，也是字典序

前序这一点可以这样理解：

1
2
3
a.push_back(i);   // 处理当前节点：记录「我做了这个选择」
calc(...);        // 再深入子节点
a.pop_back();     // 子树全部跑完，撤销选择，回到父节点的状态

五、关键区别

二叉分支版 for 多叉版
每层含义 第几个数字 第几个位置
树高 $n$ $m$
分支数 固定 2（选 / 不选） 不固定（多叉）
是否要 start 不需要 需要，用来去重
输出顺序 取决于先写「选」还是先写「不选」 天然字典序
剪枝 容易写（剩余数量不足直接砍） 只能靠 start > n 自然结束
时间复杂度 $O(2^n)$ $O(C_n^m)$
典型用途 子集类、每个元素独立决策 定长组合、按位置枚举

怎么选？

  • 想「每个数单独决定拿不拿」→ 二叉版
  • 想「答案由若干个位置拼成」→ for 多叉版

六、什么时候不是前序

偶尔会看到这种「先递归、再记录」的写法：

1
2
3
4
5
6
void calc(int pos) {
    for (int i = 1; i <= n; i++) {
        calc(pos + 1);
        a.push_back(i);   // 递归回来才记录
    }
}

这是后序风格：先钻到最深处，回来路上才把自己的选择记进数组。结果数组里是倒序的、而且无法在递归前用当前选择做剪枝，组合枚举里基本没人这么写——它违背了「进入节点时状态已经完整」这个直觉。

七、小结

二叉树递归：按数字分层，选 / 不选两个分支，树高 $n$，剪枝方便。
for 多叉版：按位置分层，start 控制起点，树高 $m$，天然去重。
两者都是前序 DFS + 回溯，只是搜索树不同。