组合枚举

一句话算法

组合枚举只关心选了哪些元素，不关心这些元素被选中的先后顺序。

问题模型

给定 n 个元素，从中选择 m 个，输出所有不同选择方案。

例如从 {1, 2, 3, 4} 中选 2 个：

1 2
1 3
1 4
2 3
2 4
3 4

1 2 和 2 1 是同一个组合，不能重复输出。

核心直觉

组合去重的关键是强制选择顺序递增。

如果上一次选了位置 last，下一次只能从 last + 1 往后选。这样每个集合只会按照从小到大的顺序出现一次。

算法步骤

1. 用 path[dep] 保存第 dep 个被选元素。
2. 定义 dfs(dep, last)：
   • dep 表示当前要选第几个元素。
   • last 表示上一次选择的下标。
3. 如果 dep > m，输出一个完整组合。
4. 否则枚举 i 从 last + 1 到可行上界：
   • 选择 a[i]。
   • 递归 dfs(dep + 1, i)。

循环上界可以剪枝为：

因为当前选了 i 后，后面还需要选 m - dep 个元素。

算法证明

关键不变量： 进入 dfs(dep, last) 时，path[1..dep-1] 中元素的下标严格递增，最后一个下标是 last。

1. 初始时没有选择元素，不变量成立。
2. 每次只枚举 i > last，所以加入新元素后，下标仍严格递增。
3. 当 dep > m 时，已经选出 m 个互不重复元素，得到一个合法组合。
4. 任意一个合法组合，把它的下标按升序写成 i1 < i2 < ... < im，DFS 会沿着这条唯一的升序路径生成它。

因此算法不会输出重复组合，也不会漏掉合法组合。

复杂度分析

组合数量是 $\binom{n}{m}$，每个组合输出 $m$ 个元素。

• 时间复杂度：$O(m \binom{n}{m})$。
• 空间复杂度：$O(m)$，用于路径和递归栈。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

// 枚举所有 m 组合。
// a 会按输入顺序被选择；如果希望字典序输出，调用前先对 a 排序。
template <class T, class Emit>
void enumerate_combinations(const vector<T>& a, int m, const Emit& emit) {
    const int n = (int)a.size();
    if (m < 0 || m > n) return;

    vector<T> path;
    path.reserve(m);

    auto dfs = [&](auto&& self, int last) -> void {
        if ((int)path.size() == m) {
            emit(path);
            return;
        }

        int need = m - (int)path.size();
        for (int i = last + 1; i <= n - need; ++i) {
            path.push_back(a[i]);
            self(self, i);
            path.pop_back();
        }
    };

    dfs(dfs, -1);
}
    

测试用例

输入：

4 2
1 2 3 4

输出：

1 2
1 3
1 4
2 3
2 4
3 4

应用分类详解

组合枚举的本质是枚举“不看顺序的选择集合”。

一、固定数量选择

典型模式： 从 n 个对象中选恰好 m 个。

识别信号： 任选若干个、选 k 个、不考虑顺序。

核心建模： 用递增下标保证每个集合只出现一次。

二、方案搜索前缀剪枝

典型模式： 选择数量固定，且部分选择已经能判断不可能。

识别信号： 选 k 个满足约束、和为目标、互不冲突。

核心建模： path 是当前选择集合，递归过程中维护约束。

经典例题

• leetcodecn-77 组合：标准固定数量组合。
• leetcodecn-216 组合总和 III：组合枚举加和剪枝。
• luogu-P1157 组合的输出：经典递增下标输出。

参考

• 本书相关章节：子集枚举