题目

Description

将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。
例如正整数6有如下11种不同的划分：
6；
5+1；
4+2，4+1+1；
3+3，3+2+1，3+1+1+1；
2+2+2，2+2+1+1，2+1+1+1+1；
1+1+1+1+1+1。

Input

多组输入EOF结束，每组输入包含一个数字n表示要拆分的数字(1<=n<=50)

Output

对于每组输入，输出所有的拆分，每个拆分一行。对于每个拆分，先输出大的数字，再输出小的数字。对于所有拆分，先输出拆分中最大数较大的，最大数相等时先输出次大数较大的....这样的顺序，具体见样例

Sample Input

5
6

Sample Output

5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1
6
5+1
4+2
4+1+1
3+3
3+2+1
3+1+1+1
2+2+2
2+2+1+1
2+1+1+1+1
1+1+1+1+1+1

题解

对于一个整数a我们对其进行拆分，可以从a里面分出小于a的所有自然数N_i。
这时，我们还需要分解a-N_i，并且以后再分解出的数不能够超过N_i
根据这个可以写出递归的函数
每加深一层递归，就把当前选择的数记录下来，当递归到最后时输出即可

如果使用int数组记录，则会导致超时
而显然算法上已经很难在优化了。
应该使用char数组来记录数据，因为直接输出字符串，比循环拼接一群int要快`

要特别注意，如果当前要记录的数i满足i>=10,那么我们将其转换成char时，需要逐位进行转换。

递归的终点是需要分解的数小于等于0
当递归到需要分解的数为0时，输出

代码

/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/
 
かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
const int maxn = 55*2*2;
char flag[maxn];
 
 
void DFS(int a,int max,int pos) {
    if(a < 0)
        return;
    if(a == 0) {
        /*for(int i = 0;i < pos;i++) {
            if(i)
                printf("+");
            printf("%d",flag[i]);
        }
        printf("\n");*/
        flag[pos - 1] = '\0';
        printf("%s\n",flag);
        return;
    }
     
    for(int i = max;i >= 1;i--) {
        //将整数i转化成char
        int pos2 = pos;
        int bit = 1;
        int j = i;
        while(j) {
            j /= 10;
            bit *= 10;
        }
        bit /= 10;
        j = i;
        while(bit) {
            flag[pos2++] = (j / bit) + '0';
            j %= bit;
            bit /= 10;
        }
        //flag[pos] = i+'0';
        flag[pos2++] = '+';
        DFS(a - i,i,pos2);
        //flag[pos] = -1;
    }
}
 
bool Do() {
    int n;
    if(scanf("%d",&n) == EOF)
        return false;
    DFS(n,n,0);
    return true;
}
 
int main() {
    while(Do());
    /*for(int i = 5;i <=6;i++)
        DFS(i,i,0);*/
    return 0;
}