递归实现组合型枚举

题目描述

从 $1 \sim n$ 中选出 $m$ 个数，输出所有选择方案。每个方案内部 $m$ 个数升序、用一个空格隔开，方案之间按字典序从小到大，每行一个方案。输入一行 $n, m$ （ $0 \le m \le n$ ， $n+(n-m) \le 25$ ）， $m=0$ 时输出一个空行。样例输入 5 3，样例输出为 1 2 3 / 1 2 4 / 1 2 5 / 1 3 4 / 1 3 5 / 1 4 5 / 2 3 4 / 2 3 5 / 2 4 5 / 3 4 5（斜杠分隔，实际每项占一行）。

思路

强制后选的数严格大于先选的数，每个组合就只有唯一一种升序写法，天然去掉重复。递归记录下一层可选的最小值 start，本层选的数最多取到 n-remaining+1，否则后面凑不够剩余个数。这样深搜的先序输出恰好就是题目要求的字典序。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 09:33
# update_at: 2026-10-01 09:33

import sys
from collections.abc import Iterator


def combine(n: int, m: int, start: int = 1) -> Iterator[tuple[int, ...]]:
    """产出从 start..n 中再选 m 个数的全部组合，按字典序依次给出。"""
    if m == 0:
        yield ()  # 一个数都不用再选，空组合本身就是一种方案
    else:
        # first 最大只能取 n-m+1，否则后面凑不够 m-1 个数
        for first in range(start, n - m + 2):
            for rest in combine(n, m - 1, first + 1):
                yield (first, *rest)


def solve() -> None:
    n, m = map(int, sys.stdin.buffer.read().split())
    print('\n'.join(' '.join(map(str, combo)) for combo in combine(n, m)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:53
 * update_at: 2026-10-06 10:55
 */
// main.cpp：从 1..n 中递归选 m 个数，按字典序输出全部组合。
#include <iostream>
using namespace std;

typedef long long ll;

ll n, m;
ll path[30]; // path[i] 表示当前方案中第 i 个选中的数

// 从 start..n 中再选 remaining 个数，当前位置是第 dep 个。
// 强制后选的数严格大于先选的数，于是行内升序、行间天然字典序。
void dfs(ll dep, ll start, ll remaining) {
    if (remaining == 0) {
        // 一个完整方案已经生成，末尾带空格输出
        for (ll i = 1; i <= m; i++) {
            cout << path[i] << ' ';
        }
        cout << '\n';
        return;
    }
    // 本层选的数 first 最大取 n - remaining + 1，否则后面凑不够剩余的个数
    for (ll first = start; first <= n - remaining + 1; first++) {
        path[dep] = first;
        dfs(dep + 1, first + 1, remaining - 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    dfs(1, 1, m);

    return 0;
}

递归实现组合型枚举

目录

题目描述

思路

参考代码