自然数的拆分问题

形式化题目

给定自然数 $n$ ，要求输出所有满足下列条件的序列：

1 \leqslant a_1 \leqslant a_2 \leqslant \cdots \leqslant a_k,\quad k \geqslant 2,\quad \sum_{i=1}^{k} a_i = n

每个序列是一行用 + 连接的加法式，所有序列按字典序从小到大输出。

暴力

先看一个可以直接验证想法的朴素解：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79/**
 * 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-08-13 13:27
 * update_at: 2026-08-13 13:29
 */
// brute.cpp：小数据暴力解，使用 01 序列 / 选择序列递归枚举所有可能。
// 把 n 看成 n 个连着的单位与它们之间的 n-1 个间隔，
// choose[i] = 1 表示把第 i 个间隔切开，切出来的每块单位数组成一个有序拆分。
// 把所有有序拆分排序去重，得到全部非递减拆分方案，再按字典序输出。
// 只适合小数据：2^(n-1) 个 01 序列，n 稍大就爆炸。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;

int n;
int choose[MAXN];  // choose[i] 表示第 i 个间隔是否切开：0 不切，1 切
vector<string> ans; // 去重后的全部非递减拆分字符串

// 由当前完整的 choose[1..n-1] 生成拆分字符串，去重后放入答案。
void calc_answer() {
    vector<int> part; // 每块的长度
    int len = 1;      // 当前块长度，第 1 个间隔前已有一个单位
    for (int i = 1; i < n; i++) {
        if (choose[i] == 1) { // 在第 i 个间隔切开，一块结束
            part.push_back(len);
            len = 1;
        } else {
            len++; // 不切开，继续累计当前块
        }
    }
    part.push_back(len); // 最后一块

    if ((int)part.size() == 1)
        return; // 只有一个块 = 方案 n 本身，题目不要求

    sort(part.begin(), part.end()); // 有序拆分排序成非递减序列

    string s;
    for (int i = 0; i < (int)part.size(); i++) {
        if (i > 0)
            s += "+";
        s += to_string(part[i]);
    }
    // 同一组加数会以多种顺序出现，这里暴力去重。
    for (int i = 0; i < (int)ans.size(); i++) {
        if (ans[i] == s)
            return;
    }
    ans.push_back(s);
}

// 这一层决定第 dep 个间隔切不切，dep 从 1 到 n-1。
void dfs(int dep) {
    if (dep == n) {
        calc_answer(); // 完整 01 序列生成后统一检查
        return;
    }
    for (int i = 0; i <= 1; i++) {
        choose[dep] = i;
        dfs(dep + 1);
    }
}

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

    cin >> n;
    dfs(1);

    sort(ans.begin(), ans.end()); // 最后统一按字典序输出
    for (int i = 0; i < (int)ans.size(); i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

这个暴力把问题看成一串 01 选择：把 n 看成 n 个连着的单位，单位之间有 n-1 个间隔，choose[i] = 1 表示切开第 i 个间隔。递归先生成完整的 choose[]，到叶子节点把切出的块长排序成非递减序列，再去重收集。它枚举了全部 $2^{n-1}$ 种有序拆分，但同一个方案会以不同顺序反复出现（如 1+2 与 2+1），只能靠排序去重补救，这就是它的瓶颈。

思路

关键观察是：一个拆分方案与它的非递减序列一一对应。如果把"下一个加数不小于上一个"直接变成递归约束，重复方案就在生成阶段被消灭，排序和去重都不再需要。

本题的正式主解是解法一（对应 main.cpp）：状态 dfs(remaining, min_val) 表示"还需凑出 remaining，下一个加数至少为 min_val"。解法二（对应 1.cpp）是同一 DFS 的另一种参数写法：dfs(pre, left, dep) 用 left 表示剩余值、pre 表示下界、dep 表示当前填到第几个加数。两种写法枚举的方案完全相同，差异只在参数的组织方式与输出细节。

解法一：状态 (remaining, min_val)

思路

用状态 dfs(remaining, min_val)：加数从 min_val 递增枚举到 remaining，选择 val 后递归 dfs(remaining - val, val)（下界传 val 本身，允许 1+1 这类重复加数）；remaining == 0 时输出当前序列，用 depth > 1 排除单项方案 n 本身。

下面这张图展示 n=4 时的部分搜索树：

text

1
2
3
4
5
6
7
8
9            状态 (剩余, 下界)
            (4,1)
            ├─ 选 1 → (3,1)
            │   ├─ 选 1 → (2,1)
            │   │   ├─ 选 1 → (1,1) ── 选 1 → 1+1+1+1
            │   │   └─ 选 2 → (0,2) ── 输出 1+1+2
            │   └─ 选 2 → (1,2) ── 无可选（2 > 1）→ 死路
            ├─ 选 2 → (2,2) ── 选 2 → (0,2) ── 输出 2+2
            └─ 选 3 → (1,3) ── 死路（选 4 即单项方案，被排除）

从图中可以看到，每个节点的下界由上一个加数决定，所以 1+2 之后不可能再选 1；到达 (0, 下界) 的叶子就输出一条方案，死路分支是"剩余和小于下界"时自动发生的。

代码

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
44
45
46
47
48/**
 * 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-08-13 13:27
 * update_at: 2026-08-13 13:29
 */
/* P2404 自然数的拆分问题 */
/* DFS 枚举非递减加数序列：每一层选择下一个加数，要求不小于上一个。 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15; // n <= 8，全 1 拆分时序列最长也只有 n 项

int n;
int path[MAXN]; // path[1..depth] 保存当前拆分序列
int depth;      // 当前序列长度

// 还需凑出 remaining，下一个加数至少为 min_val
void dfs(int remaining, int min_val) {
    if (remaining == 0) {
        if (depth > 1) { // 排除只有 n 本身的单项方案
            for (int i = 1; i <= depth; i++) {
                if (i > 1)
                    cout << "+";
                cout << path[i];
            }
            cout << "\n";
        }
        return;
    }

    for (int val = min_val; val <= remaining; val++) {
        path[++depth] = val;
        dfs(remaining - val, val); // 下一项不小于 val，保证序列非递减
        depth--;
    }
}

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

    cin >> n;
    dfs(n, 1);
    return 0;
}

Guide 风格代码

cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：

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
44/**
 * 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-08-14 15:08
 * update_at: 2026-08-14 15:08
 */
#include <iostream>

const int max_n = 15; // n <= 8，全 1 拆分时序列最长也只有 n 项

int n;
int path[max_n]; // path[0..depth-1] 保存当前拆分序列
int depth = 0;   // 当前序列长度

// 还需凑出 remaining，下一个加数至少为 min_val
void dfs(int remaining, int min_val) {
    if (remaining == 0) {
        if (depth > 1) { // 排除只有 n 本身的单项方案
            for (int i = 0; i < depth; i += 1) {
                if (i > 0) {
                    std::cout << '+';
                }
                std::cout << path[i];
            }
            std::cout << '\n';
        }
        return;
    }

    // 加数从小到大尝试，下一个不小于当前值，保证序列不下降
    for (int val = min_val; val <= remaining; val += 1) {
        path[depth] = val;
        depth += 1;
        dfs(remaining - val, val);
        depth -= 1; // 恢复现场：撤销这次选择，再尝试下一个加数
    }
}

int main() {
    std::cin >> n;
    dfs(n, 1);
    return 0;
}

复杂度

输出方案数等于整数拆分数 $p(n)$ （去掉单项后为 $p(n)-1$ ），搜索树节点数与其同阶，每个方案输出需要 $O(n)$ 时间，所以总时间复杂度为 $O(\text{方案数} \times n)$ ；本题 $n \leqslant 8$ ， $p(8)=22$ ，规模极小。空间为递归深度 $O(n)$ 。

解法二：状态 (pre, left, dep)

思路

dfs(pre, left, dep) 是同一非递减 DFS 的另一种参数组织：left 直接表示"还剩多少没拆"，pre 是下一个加数的下界，dep 是当前方案长度（同时用作输出游标）。枚举范围同样是 i ∈ [pre, left]，left == 0 时输出方案，并用 dep == 2 排除单项方案。

与解法一的差别只在接口形态：解法一把状态拆成"剩余 + 下界"两个量，解法二再把"已经填了几个加数"显式拿出来；对拍两种实现输出完全一致。

代码

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/**
 * 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-28 17:27
 * update_at: 2026-08-13 14:10
 */
// 1.cpp：自然数拆分的另一种 DFS 写法。
// 与 main.cpp 同一思路（加数非递减），区别在参数形式：dfs(pre, left, dep)
// 直接用 left 表示"还剩下多少要拆"，pre 是下一个加数的下界。
#include <bits/stdc++.h>
using namespace std;

int n;
int a[100005]; // a[dep]：当前方案第 dep 个加数

// 已确定前 dep-1 个加数，下一个加数至少为 pre，还剩下 left 没有拆。
void dfs(int pre, int left, int dep) {
    // 拆完：left == 0，输出方案。
    if (left == 0) {
        // 只有一项（dep == 2 表示只拆出 n 本身）不输出，题目要求至少两个加数。
        if (dep == 2)
            return;
        for (int i = 1; i <= dep - 2; i++)
            cout << a[i] << "+";
        cout << a[dep - 1] << "\n";
        return;
    }

    // 枚举下一个加数 i：不小于 pre（保证非递减去重），且不超过剩余的 left。
    for (int i = pre; i <= left; i++) {
        a[dep] = i;
        dfs(i, left - i, dep + 1);
    }
}

int main() {
    std::cin >> n;
    dfs(1, n, 1);

    return 0;
}

复杂度

与解法一相同： $O(\text{方案数} \times n)$ 时间， $O(n)$ 空间。

复杂度对比

方案	状态	排除单项的方式	输出格式
解法一 main.cpp	`(remaining, min_val)`	`depth > 1`	循环输出
解法二 1.cpp	`(pre, left, dep)`	`dep == 2`	先输出 `dep-2` 个带 `+`，再输出末项

两种写法的枚举对象与方案序列完全相同，选哪一种只是个人风格问题。

总结

通过给下一层设置"不得小于上一项"的下界，可以在生成阶段直接保证方案唯一，不需要最后再用集合去重或排序；加数从小到大枚举又自然满足字典序输出要求。这道题是"选择序列 DFS + 有序化约束"最直接的入门例子：把约束写进状态而不是写进过滤逻辑，是它和 brute.cpp 的本质区别。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18暴力（brute.cpp）
  01 序列 choose[1..n-1] 枚举 n-1 个间隔切/不切 → 2^(n-1) 种有序拆分
  每个拆分排序成非递减序列，再线性扫描去重，最后统一排序输出
        |
        | 瓶颈：同一方案以多种顺序反复出现，全靠排序 + 去重补救
        v
关键观察
  一个拆分方案 ⇔ 唯一一个非递减序列
  把“下一个加数不小于上一个”写进递归下界，重复从生成源头消失
        |
        v
正式解（解法一 main.cpp / 解法二 1.cpp）
  dfs(remaining, min_val)  或  dfs(pre, left, dep)
  每层选 val ∈ [min_val, remaining]，加数从小到大 → 输出天然字典序
  remaining == 0 / left == 0 时输出，并排除单项 n
        |
        v
复杂度与整数拆分数 p(n) 同阶，n ≤ 8 时 p(8) = 22，规模极小

上半部分是"先枚举后过滤"的暴力模型，下半部分是"生成即唯一"的正式模型，两者的分界点正是"一个拆分方案与它的非递减序列一一对应"这个观察；把约束写进状态而不是写进过滤逻辑，是整道题的核心做法。