洛谷P2404 自然数的拆分问题

题目描述

任何一个大于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      

说明/提示

用回溯做。。。。

n≤8

上代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[10001];
int sum=0;
void print(int step)
{
    sum++;
    
    for(int i=1;i<step;i++)
        cout<<a[i]<<"+";
    cout<<a[step]<<endl;
}
void searchh(int s,int step)
{
    for(int i=a[step-1];i<=s;i++)//当前数i要大于等于前1位数，且不超过n
    {
        if(i<n)
        {
            a[step]=i;
            s-=i;
            if(s==0) print(step);
            else searchh(s,step+1);
            s+=i;
 
        }
    }
}
int main()
{
    for(int i=0;i<=10000;i++)
        a[i]=1;
    cin>>n;
 
    searchh(n,1);
    return 0;
}