题目描述】
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。
当n=7共14种拆分方法：
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
total=14【输入】
输入n。
【输出】
按字典序输出具体的方案。
【输入样例】
7【输出样例】
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
#include <iostream>
using namespace std;
int a[100],n;
void dfs(int sum,int cnt)
{
if(sum>n)
return;
if(sum==n)
{
cout<<n<<"=";
for(int i=1;i<cnt-1;i++)
cout<<a[i]<<"+";
cout<<a[cnt-1];
cout<<endl;
return;
}
for(int i=1;i<n;i++)
{
if(i>=a[cnt-1]) //不加此行，分成全排列 例如 此行要求后面的数一定要大于等于前面一个数
{
a[cnt]=i;
dfs(sum+i,cnt+1);
}
}
}
int main()
{
cin>>n;
dfs(0,1);
return 0;
}
标签：cnt,5.3,int,sum,自然数,dfs,1318,拆分,csp From： https://www.cnblogs.com/nanshaquxinaosai/p/18413274