P2404 自然数的拆分问题（DFS）

P2404 自然数的拆分问题（DFS）

Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 55     Solved: 38

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

Input 输入一个整数 n（1 <= n <= 8），表示需要拆分的自然数。

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

Hint 为了保证“字典序”，限制下一层枚举的加数不小于前一层。

AC代码

#include<iostream>
using namespace std;
int n;
const int maxn=33;
int arr[maxn];
int ans;
void dfs(int front,int step,int sum)
{
    if(sum==0)
    {
        if(step==1)return;
        for(int i=0;i<step-1;i++)cout<<arr[i]<<"+";
        cout<<arr[step-1]<<endl;
        return ;
    }
    for(int i=front;i<=sum;i++)
    {
        arr[step]=i;
        if(sum-i>=0)dfs(i,step+1,sum-i);
    }

}
int main()
{
    int n;
    while(cin>>n)
    {
        dfs(1,0,n);
    }
    return 0;
}