【例5.2】组合的输出

题目描述

从 $n$ 个元素（即自然数 $1,2,\dots,n$ ）中取出 $r$ 个数（ $1 \leqslant r \leqslant n$ ，不分顺序），用递归的方法输出所有组合。每个组合占一行，元素按从小到大排列；所有组合按字典序输出。

输入：一行两个自然数 $n$ 、 $r$ 。

输出：所有组合，每个数占三个字符的位置（固定两个空格 + 十进制）。

样例输入 5 3 对应的输出从 1 2 3 开始，共 $\binom{5}{3}=10$ 行，最后一行为 3 4 5。

思路

组合就是严格递增序列：递归逐位选数，第 $k$ 位必须大于第 $k-1$ 位，递增性天然保证不重不漏（不需要 vis 数组）。层内从小到大枚举，前序输出顺序恰好就是字典序；再剪枝——还要取 $h$ 个数时，本位最大到 $n-h+1$ 。输出格式注意「占三个字符」实为固定两个空格加十进制，用 %3d 右对齐会在两位数处出错。

参考代码

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
30#!/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-09-30 04:53
# update_at: 2026-09-30 04:53

import sys


def combos(n: int, r: int):
    """按字典序递归产出 1..n 中取 r 个的严格递增组合。"""
    if r == 0:  # 不再取数：当前前缀就是一个完整组合
        yield ()
        return
    # 还要取 r 个数，下一个数最大只能到 n-r+1，否则后面取不满
    for head in range(1, n - r + 2):
        for tail in combos(n - head, r - 1):  # 从 head+1..n 里再取 r-1 个（平移成 1..n-head）
            yield (head,) + tuple(head + value for value in tail)


def solve() -> None:
    n, r = map(int, sys.stdin.buffer.read().split())
    # 题面的「占三个字符」实为标准程序的 "  "+十进制：两位数多占一格
    lines = (''.join(f'  {value}' for value in combo) for combo in combos(n, r))
    sys.stdout.write('\n'.join(lines) + '\n')


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/**
 * 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-05 09:17
 * update_at: 2026-10-05 09:17
 */

// 组合的输出：从 1..n 中按字典序输出所有 r 元组合（递归实现）。

#include <cstdio>

typedef long long ll;

const int MAXR = 25;

ll n, r;
int choose[MAXR]; // choose[i] 表示组合中第 i 个数（严格递增）

// 这一层在选组合的第 dep 个数：从上一个数+1 枚举到 n，保证严格递增
// 递增性天然保证不重不漏，且首元从小到大枚举即得字典序
void dfs(ll dep, ll last) {
    if (dep > r) { // r 个数已选满，输出当前组合
        for (ll i = 1; i <= r; i++) {
            printf("  %d", choose[i]); // 固定两个空格 + 十进制：两位数自然占 3 列
        }
        printf("\n");
        return;
    }
    // 剪枝：还要取 r-dep+1 个数，最后一个数最大到 n-(r-dep+1)+1
    for (ll v = last + 1; v <= n - (r - dep + 1) + 1; v++) {
        choose[dep] = v;
        dfs(dep + 1, v);
    }
}

int main() {
    scanf("%lld %lld", &n, &r);
    dfs(1, 0); // 从「上一个数是 0」开始，即第一个数从 1 枚举
    return 0;
}

【例5.2】组合的输出

目录

题目描述

思路

参考代码