洛谷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;
}