【题目来源】
【题目描述】
给定自然数 n，将其拆分成若干自然数的和。输出所有解，每组解中数字按从小到大排列。相同数字的不同排列算一组解。
如，读入整数 3，分解方案如下：
1+1+1
1+2
再比如，读入整数 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【输入格式】
一个整数 n（n≤20）；
【输出格式】
n 可以分解的自然数和的方案；
【输入样例】
3
【输出样例】
1 1 1
1 2
【数据范围】
n≤20
【算法分析】
● 这个 dfs(int sum, int step) 函数设计了“分解步骤”和“枚举加数”两个核心操作。
首先，考虑一个数值的拆分问题。比如要拆分整数n，每次枚举一个要减去的数字 i，作为拆分的一部分。枚举时，为了不产生如“1+2”和“2+1”这种仅仅是顺序不同的重复结果，函数使用了一个关键技巧：枚举下一个加数时，起点从上一个加数开始。这保证了所有加数序列都是非递减的，从而避免重复。
其次，从“剩余数值”的角度去理解递归过程会更直观。函数参数 sum 代表当前的“余额”，而 step 记录当前是第几个加数。每层递归的主要工作是根据规则枚举加数。如果找到一个加数i使余额 sum 恰好减到 0，就输出一组解；否则用新的余额继续递归。
● 这个 dfs(int sum, int step) 函数的思路，本质上是在构建一棵“搜索树”，每一次选择（即加数 i）都会生成一条新的分支。递归的“深度”对应着拆分出的加法项数，而“回溯”操作（sum+=i）则是在完成一条路径的探索后，撤销上一步的选择，以便在同层尝试其他可能的分支。通过这种方式，函数系统地枚举了所有符合规则的加数组合，最终得到所有拆分方案。
● 下面代码，是“洛谷 P2404：自然数的拆分问题”（）的代码。将其中的 cout<<a[i]<<"+"; 改为 cout<<a[i]<<" "; 便可适用于本题。
【算法代码一】
#include <bits/stdc++.h>
using namespace std;const int maxn=25;
int a[maxn];void print(int step) {for(int i=1; i<step-1; i++) {cout<<a[i]<<"+";}cout<<a[step-1]<<endl;
}void dfs(int sum, int step, int start) {if(sum==0) {if(step>2) print(step);return;}for(int i=start; i<=sum; i++) {a[step]=i;dfs(sum-i,step+1,i);}
}int main() {int n;cin>>n;dfs(n,1,1);return 0;
}/*
in:
5out:
1+1+1+1+1
1+1+1+2
1+1+3
1+2+2
1+4
2+3
*/
【算法代码二】
#include <bits/stdc++.h>
using namespace std;const int maxn=25;
int a[maxn];
int n;void print(int step) {for(int i=1; i<step; i++) {cout<<a[i]<<"+";}cout<<a[step]<<endl;
}//sum为剩余数值，step为当前拆分的步数
void dfs(int sum, int step) {for(int i=a[step-1]; i<=sum; i++) {if(i<n) {a[step]=i;sum-=i;if(sum==0) print(step);else dfs(sum, step+1);sum+=i;}}
}int main() {a[0]=1;cin>>n;dfs(n,1);return 0;
}/*
in:
7out:
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
*/
【参考文献】