【题目来源】
洛谷：P2404 自然数的拆分问题 - 洛谷
【题目描述】
任何一个大于 \(1\) 的自然数 \(n\)，总可以拆分成若干个小于 \(n\) 的自然数之和。现在给你一个自然数 \(n\)，要求你求出 \(n\) 的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。
【输入】
输入：待拆分的自然数 \(n\)。
【输出】
输出：若干数的加法式子。
【输入样例】
7
【输出样例】
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4
【解题思路】
【算法标签】
《洛谷 P2404 自然数的拆分问题》 #搜索#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n; // 输入的需要分解的正整数
int a[10]; // 存储当前分解方案的数组/*** 深度优先搜索函数，用于生成所有可能的分解方案* @param s 剩余需要分解的数值* @param step 当前分解的步骤（即当前分解出的数字个数）*/
void dfs(int s, int step)
{// 当剩余数值为0时，表示找到一个有效的分解方案if (s == 0) {// 输出分解方案，用"+"连接各个数字for (int i = 0; i < step - 1; i++) {cout << a[i] << "+";}cout << a[step - 1] << endl; // 输出最后一个数字并换行return;}// 尝试所有可能的分解数字（从1到剩余数值s）for (int i = 1; i <= s; i++) {// 确保分解的数字不小于前一个数字（避免重复方案）if (i < a[step - 1]) {continue;}// 记录当前分解的数字a[step] = i;// 递归处理剩余数值dfs(s - i, step + 1);}
}int main()
{// 输入需要分解的正整数cin >> n;// 从1开始尝试所有可能的第一个分解数字for (int i = 1; i <= n / 2; i++) {a[0] = i; // 设置第一个分解数字dfs(n - i, 1); // 递归处理剩余数值}return 0;
}
【运行结果】
7
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4