将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编程求出正整数N的所有整数分解式子。

输入格式：

每个输入包含一个测试用例，即正整数N (0

输出格式：

按递增顺序输出N的所有整数分解式子。递增顺序是指：对于两个分解序列N_1={_n_1,_n_2,⋯}和_N_2={_m_1,_m_2,⋯}，若存在_i使得n_1=_m_1,⋯,_n__i=m__i，但是n__i+1<_m__i_+1,则_N_1序列必定在_N_2序列之前输出。每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。

输入样例：

  1. 7

输出样例：

  1. 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
  2. 7=1+1+1+4;7=1+1+2+3;7=1+1+5;7=1+2+2+2
  3. 7=1+2+4;7=1+3+3;7=1+6;7=2+2+3
  4. 7=2+5;7=3+4;7=7
  1. 其实用数字直接表示这个结果看起来就很直观了
  3. 1 1 1 1 1 1 1 
  4. 1 1 1 1 1 2
  5. 1 1 1 1 3
  6. 1 1 1 2 2
  7. 1 1 1 4
  8. 1 1 2 3
  9. 1 1 5
  10. 1 2 2 2 
  11. 1 2 4
  12. 1 3 3
  13. 1 6
  14. 2 2 3
  15. 2 5
  16. 3 4
  17. 7
  1. //一直没思路 看百度ing
  2. #include<stdio.h>
  4. //深度优先DFS 遍历 
  5. //启发很大 https://www.cnblogs.com/andywenzhi/p/5738715.html
  6. //好家伙 算是默写下来了
  8. int n;
  10. int s[31];
  11. int top = -1;
  12. int cnt = 0;
  13. int sum = 0;
  15. void dfs(int i);
  17. int main()
  18. {            
  19.     scanf("%d", &n);
  21.     dfs(1);
  23.     return 0;
  24. }
  26. void dfs(int i){
  28.     if(sum==n)
  29.     {
  30.         cnt++;
  31.         printf("%d=", n);
  32.         for(int k=0; k<top; k++)
  33.             printf("%d+", s[k]);
  35.         if(cnt%4==0 || s[top]==n)//如果漏掉s[top]==n的话无法通过 
  36.                 printf("%d\n", s[top]);//输出表达式最末尾的栈顶 
  37.         else
  38.                 printf("%d;", s[top]); 
  40.         return;            
  41.     }
  43.     if(sum>n)
  44.     {
  45.         return;
  46.     }     
  48.     for(int j=i; j<=n; j++)//只有sum<n时运行 j=i?
  49.     {
  50.         s[++top] = j;
  51.         sum += j;
  52.         dfs(j);//这里改为dfs(i)会怎样? 
  53.         sum -= j;
  54.         top--;
  55.     } 
  56. }
  1. 本质上其实不难 但是为什么我理解不了 
  2. 手算推一下
  4. 第一轮
  5. 1111111→1111112→1111113→1111114→1111115→1111116→1111117 输出(1(1(1(1(1(1(1
  6. 第二轮
  7. 111112→111113→111114→11115→111116→111117 输出(1(1(1(1(1(2
  8. 第三轮
  9. 11113→ … 输出(1(1(1(1(3 
  10. 第四轮
  11. 11122
  12. 以此类推
  17. 等以后完善