P2404 splitting of natural numbers

  Copy Markdown   an

Title Description

Any one is greater than  11  The natural number of  nn, It can be divided into several smaller than  nn  The sum of the natural numbers of . Now I'll give you a natural number  nn, Ask you to find out  nn  Split into some numbers and . The numbers in each split sequence are sorted from small to large . Then you need to output these sequences , Among them, the sequence with small dictionary order needs to be output first .

Input format

Input ： Natural number to be split  nn.

Output format

Output ： The addition formula of some numbers .

I/o sample

Input #1 Copy

7

Output #1 Copy

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

explain / Tips

Data assurance ,1<=n<=8

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
int a[10001]= {1};
int n;
void print(int t)
{
    for(int i=1; i<=t-1; i++)
        cout<<a[i]<<"+";
    cout<<a[t]<<endl;
}
void dfs(int s,int t)
{
    for(int i=a[t-1]; i<=s; i++)// Greater than or equal to the previous digit 
    {
        if(i<n)
        {
            a[t]=i;
            s-=i;
            if(s==0) print(t);
            else dfs(s,t+1);
            s+=i;
        }
    }
}
int main()
{
    cin>>n;
    dfs(n,1);

    return 0;
}