拆分自然数

题目描述任何一个自然数n，总可以拆分成若干个自然数之和。当n=7共15种拆分方法：7=1+1+1+1+1+1+17=1+1+1+1+1+27=1+1+1+1+37=1+1+1+2+27=1+1+1+47=1+1+2+37=1+1+57=1+2+2+27=1+2+47=1+3+37=1+67=2+2+37=2+57=3+47=7total=15输入格式一行一个整数n。输出格式所有拆分方案，具体格式见【样例】。样例数据input4output1+1+1+11+1+21+32+24total=5数据规模与约定1≤n≤20

CODE

#includeusing namespace std;int a[25],n;int cnt=0,tot=0;//tot表示a数组的最后一个数的下标 void dfs(int x,int r)//r表示a数组的最后的一个数值 {int t;if(x==0){cnt++;for(int j=1;j<=tot-1;j++){cout<<a[j]<<'+';}cout<<a[tot]<<endl;return;}    t=x/2;for(int i=r;i<=t;i++){tot++;a[tot]=i;dfs(x-i,i);tot--;}tot++;a[tot]=x;dfs(0,x);tot--;}int main(){cin>>n;dfs(n,1);cout<<"total="<<cnt<<endl;return 0;}

明天再见，拜拜！！