自然數的拆分問題:
Time Limit:1000ms Memory Limit:32KB 64bit IO Format: %lld

Description
任何一個大於1的自然數n,總可以拆分成若干個小於n的自然數之和。

Input
待拆分的自然數n。

Output
若干個數的加法式子。

Sample Input
7

Sample Output
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

code

# include <iostream>
# include <vector>
# include <cstdio>

using namespace std;

vector<int> res;
int s, n;

void dfs(int last)
{
    if(s == 0)
    {
        for(int i = 1; i <= res.size() - 2; i ++) printf("%d+" , res[i]);
        cout << res[res.size() - 1] << endl;
    }

    for(int i = last; i < n; i ++)
    {
        if(s >= 1)
        {
            s -= i;
            res.push_back(i);
            last = i;
            dfs(last);
            s += i;
            res.pop_back();
            last = 1;
        }
    }
}
int main()
{
    cin >> n;
    s = n;
    res.push_back(0);

    dfs(1); 

    return 0;
}