组合：选人不排队，只看选谁不看顺序

想象一下，班里要从5个同学里选出3个人一起去搬花盆。选小明、小红、小刚，还是选小红、小刚、小明，其实都是同样的3个人，谁先谁后根本没区别。这种“只关心选了哪些人，不关心顺序”的选法，数学上就叫组合。

生活中到处都是组合的例子：从3种零食（薯片、巧克力、糖果）里挑两种带走，选“薯片+巧克力”和选“巧克力+薯片”是一种组合；从10道题里选5道来做，顺序不重要，只关心选了哪几道。而排列则恰恰相反，它要管顺序，比如站队时的先后位置、比赛的名次等。

这篇文章会用C++教你如何把所有的组合“列”出来，让你一看就懂。

什么是组合？和排列有什么不同？

组合的定义很简单：从 n 个不同的元素中，任取 m 个元素（m ≤ n），不管顺序，组成一组，叫做一个组合。所有这样不同的组的总数，记作 C(n, m) 或 $\binom{n}{m}$ ，读作“n 选 m”。

数学公式：

C(n, m) = \frac{n!}{m! \cdot (n-m)!}

比如从 4 个同学（小明、小红、小刚、小丽）中选 2 个，共有多少种选法？

计算公式：4! / (2! × 2!) = 24 / (2 × 2) = 6 种。
具体组合：小明+小红、小明+小刚、小明+小丽、小红+小刚、小红+小丽、小刚+小丽。注意，“小明+小红”和“小红+小明”只算一种。

对比排列：如果是排列（选两个人站成一排），则“小明在前，小红在后”和“小红在前，小明在后”是两种不同的排列，总数是 P(4,2) = 4 × 3 = 12。

组合只关心“谁被选中”，排列还关心“谁站哪个位置”。这就是最核心的区别。

怎么用C++生成所有组合？——二进制枚举法

计算机里，我们经常需要把所有的组合都列出来，比如测试数据、穷举方案等。一个非常直观的方法就是用“二进制”来模拟每个元素“选或不选”。

原理：二进制位表示选或不选

假设有 n 个元素，我们给每个元素编个号：0, 1, 2, …, n-1。用一个 n 位的二进制数（比如 01010）来表示：第 i 位是 1 表示选第 i 个元素，是 0 表示不选。那么，所有 n 位二进制数（从 000…0 到 111…1）就对应了所有可能的子集（包括空集和全集）。我们只需要从中挑出二进制中 1 的个数恰好等于 m 的那些二进制数，就得到了所有组合。

例如，从 3 个元素（A、B、C）中选 2 个：

二进制数 011（十进制 3）：第0位=1（选A），第1位=1（选B），第2位=0（不选C）→ 组合 {A, B}
二进制数 101（十进制 5）：A和C → {A, C}
二进制数 110（十进制 6）：B和C → {B, C}

这样，用循环枚举所有二进制数，再统计1的个数，就能轻松得到所有组合。

代码一步步拆解

下面用一组生活例子：有5个零食编号1~5，想选出3个。我们来写代码。先看完整的代码（后面会逐行解释）：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 5;                     // 总共有5种零食
    int m = 3;                     // 要选出3种
    vector<int> items = {1, 2, 3, 4, 5}; // 零食编号列表

    cout << "所有组合（从1~5中选3个）：" << endl;
    // 枚举所有子集：从0到 (1<<n)-1
    for (int mask = 0; mask < (1 << n); mask++) {
        // 统计当前mask中二进制1的个数
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) cnt++;
        }
        // 如果1的个数恰好等于m，则输出该组合
        if (cnt == m) {
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    cout << items[i] << " ";
                }
            }
            cout << endl;
        }
    }
    return 0;
}

逐行解释：

int n = 5; 总共有几样东西。这里我们选了5种零食。
int m = 3; 要选几样。这里选3样。
vector<int> items = {1, 2, 3, 4, 5}; 具体有哪些东西，可以是编号、名字或任意数据。
for (int mask = 0; mask < (1 << n); mask++)：(1 << n) 等于 $2^n$ ，这里是 32。所以 mask 从 0 跑到 31，覆盖了所有 5 位二进制数（00000 ~ 11111）。
内层循环 for (int i = 0; i < n; i++) 逐位检查 mask 的二进制：mask & (1 << i) 可以判断第 i 位是否为 1。如果为 1，cnt 加 1。
当 cnt == m 时，说明这个 mask 正好选了 m 个元素，就输出对应的 items[i]（注意：items[i] 对应第 i 个零食，比如 i=0 对应 1，i=1 对应 2，……）。

运行这段代码，你会看到输出（共 10 行）：

注意：组合内的数字是从小到大的，这是因为我们按 i 从 0 到 4 顺序输出，而 mask 中的 1 位对应的下标也是从小到大，所以自然有序。但组合之间的顺序是按二进制数从小到大排列的，不是字典序（比如 1 4 5 出现在 2 3 4 之前）。

为了更贴近生活，你可以把 items 改成零食名字：

vector<string> items = {"薯片", "巧克力", "糖果", "饼干", "果冻"};

输出就会变成 “薯片巧克力糖果” 这样的组合。

常见错误提醒

1. 位运算的括号问题
写 if (mask & (1 << i)) 时，括号不能省。因为 & 优先级比 == 低，如果不加括号，mask & (1 << i) 可能被错误解析。新手容易写成 if (mask & 1 << i == 0) 之类，结果完全不对。

2. 整数溢出
当 n 比较大时（比如 n = 31 或 32），1 << n 可能超出 int 范围（int 通常 32 位，1<<31 是负数，1<<32 是未定义行为）。稳妥的做法是用 unsigned int 或 long long，或者限制 n ≤ 30。对于 n > 30，二进制枚举太慢（2^31 约 21 亿次），不适合。

3. 统计1的个数用循环太慢？
对于小规模 n（比如 n ≤ 20），两层循环完全够用。如果追求效率，可以用内置函数 __builtin_popcount(mask) 或 bitset，但那是进阶内容。

4. 忘记输出空格或换行
在输出组合内元素时，如果你直接用 cout << items[i] 而不加空格，所有数字会连在一起。同样，每组组合结束后要记得换行（cout << endl;），否则结果都挤在一行。

完整代码示例（带详细注释）

下面的代码直接从1~5中选3个，你可以复制到电脑上运行，看看效果。

#include <iostream>
#include <vector>   // 使用vector容器
using namespace std;

int main() {
    int n = 5;                     // 元素总数
    int m = 3;                     // 选出多少个元素
    vector<int> items = {1, 2, 3, 4, 5}; // 所有元素（这里是1~5的数字）

    cout << "所有组合（从1~5中选3个）：" << endl;

    // 枚举所有可能的子集（用二进制表示）
    for (int mask = 0; mask < (1 << n); mask++) {
        // 统计当前子集中1的个数，即选中的元素个数
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {   // 检查第i位是否为1
                cnt++;
            }
        }
        // 如果个数正好等于m，输出这个组合
        if (cnt == m) {
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    cout << items[i] << " ";  // 输出选中的元素
                }
            }
            cout << endl;  // 每组组合换一行
        }
    }
    return 0;
}

运行结果（10行）：

组合：选人不排队