转载请注明出处

题目描述

对于大于1的自然数N，可以拆分成若干个大于等于1的自然数之和。

Input

一个大于1的自然数N

Output

所有的拆分情况.按字典序排列。

Sample Input

6

Sample Output

6=1+1+1+1+1+16=1+1+1+1+26=1+1+1+36=1+1+2+26=1+1+46=1+2+36=1+56=2+2+26=2+46=3+36=6

Hint

注意观察数字的变化规律 

同一层的数从左往右，从右往左都分析下。 

上下两层的关系也分析下

1 /** 2     网址：http://www.codeup.cn/problem.php?id=2910 3     题目：自然数的拆分问题 字典序 4 */ 5  6 #include 
      
        7 int N; 8 int result[100]; 9 10 void print(int n){11     int i;12     printf("%d=",N);13     for(i = 0; i < n - 1; i++){14         printf("%d+",result[i]);15     }16     printf("%d\n",result[i]);17 }18 19 /**20     cur:当前要填的数字21     leave:差22 */23 void search(int cur,int leave){24     if(leave <= 0){25         print(cur);26         return ;27     }28 29     for(int i = 1; i <= N; i++){30         if(leave >= i && i >= result[cur - 1]){31             result[cur] = i;32             search(cur + 1, leave - i);33 34         }35         if(leave < i)36             break;37 38     }39 }40 41 int main(void){42     while(scanf("%d",&N) != EOF){43         search(0,N);44     }45     return 0;46 }