题目

题目描述

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n，要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。

输入格式

输入：待拆分的自然数n。

输出格式

输出：若干数的加法式子。

输入输出样例

输入 #1复制

7

输出 #1复制

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

解题思路：

其实这题我的想法很简单，就是不停的拆分，直到不能拆，用递归，还要记得回溯，实现所有可能的拆分。

代码展示：

#include<stdio.h>
int A[10000]={1};
//在下面fun函数中需要从A数组中前一个数开始循环，进行拆分，所以要对A数组赋值为1
int n;
void print(int n)
{int i;for(i=1;i<=n-1;i++)printf("%d+",A[i]);printf("%d\n",A[n]);//方便换行
}
void fun(int a,int b)
{int i;for(i=A[b-1];i<=a;i++)//i要大于前面一个数，小于n{if(i<n)//小于n{A[b]=i;//把拆出来的数存在数组中a=a-i;//减去已经拆分出来的数，剩下的继续拆分if(a==0)//为0时结束拆分print(b);else fun(a,b+1);//继续重复操作a=a+i;//回溯，加上已经拆分的数，实现所有可能的拆分}}
}
int main()
{scanf("%d",&n);fun(n,1);return 0;
}

运行结果：