组合型枚举(Combination Enumeration) 题解

思路分析

设计递归函数 dfs(idx, start) 表示正在确定第 idx 个位置（$1 \sim m$），且当前可选最小数字为 start。剪枝条件：若剩余可选数字个数 n - start + 1 < m - idx + 1 则直接返回。从小到大枚举当前数字 i（start <= i <= n），不仅保证行内严格递增，而且天然按字典序从小到大输出所有 $\binom{n}{m}$ 种方案。

参考代码

#include <iostream>
using namespace std;

int n, m;
int chosen[30];

void dfs(int idx, int start)
{
    if (n - start + 1 < m - idx + 1) return;
    if (idx > m)
    {
        for (int i = 1; i <= m; ++i)
        {
            if (i > 1) cout << " ";
            cout << chosen[i];
        }
        cout << "\n";
        return;
    }
    for (int v = start; v <= n; ++v)
    {
        chosen[idx] = v;
        dfs(idx + 1, v + 1);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m)) return 0;
    dfs(1, 1);
    return 0;
}