自然数的拆分

题目描述

输入一个大于 1 的自然数 $n$ ，把 $n$ 拆分成若干小于 $n$ 的正整数之和，按字典序输出所有不同的拆分方案。顺序不同视为同一种方案。

思路

DFS 枚举时限制下一个加数不小于上一个加数，这样每种无序拆分只出现一次，且从小到大枚举天然满足字典序。剩余值为 0 时输出当前方案。

参考代码

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
31
32
33
34
35#!/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-07-05 21:47
# update_at: 2026-07-05 21:47

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)
    if n is None:  # 空输入防御：没有位置量就直接结束
        return
    out: list[str] = []

    def dfs(rest: int, start: int, path: list[int]) -> None:
        """按非递减顺序搜索 rest 的拆分，path 记录已选加数。"""
        if rest == 0:
            out.append(f"{n}={'+'.join(map(str, path))}")
            return
        # 下一个加数不小于上一个（保证不重复），且必须小于 n
        for x in range(start, rest + 1):
            if x < n:
                path.append(x)
                dfs(rest - x, x, path)
                path.pop()

    dfs(n, 1, [])
    sys.stdout.write('\n'.join(out))


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/**
 * 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
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 1000; // 拆分路径长度上界

ll n;             // 待拆分的自然数
ll path[MAXN];    // 当前拆分方案

// 按非递减顺序搜索 rest 的拆分，start 为下一个加数的最小允许值，len 为已选加数个数
void dfs(ll rest, ll start, int len) {
    if (rest == 0) {
        printf("%lld=%lld", n, path[0]);
        for (int i = 1; i < len; ++i) {
            printf("+%lld", path[i]);
        }
        putchar('\n');
        return;
    }
    for (ll x = start; x <= rest; ++x) {
        if (x < n) {          // 每个加数必须小于 n
            path[len] = x;
            dfs(rest - x, x, len + 1);
        }
    }
}

int main() {
    scanf("%lld", &n);
    dfs(n, 1, 0);
    return 0;
}

目录

题目描述

思路

参考代码