題目描述

任何一個大于?11?的自然數?n，總可以拆分成若干個小于?n?的自然數之和。現在給你一個自n，要求你求出?n?的拆分成一些數字的和。每個拆分后的序列中的數字從小到大排序。然后你需要輸出這些序列，其中字典序小的序列需要優先輸出。

輸入格式

輸入：待拆分的自然數?n。

輸出格式

輸出：若干數的加法式子。

樣例輸入

7

樣例輸出

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

說明/提示

數據保證，2 ≤ n ≤ 8。

參考代碼

#include<bits/stdc++.h>
using namespace std;
int a[100],n,m;
void dfs(int d, int p, int sum)
{if(sum == n) {for(int i = 1; i <= d - 1; i++) {cout<<a[i];if(i != d - 1)cout<<"+";}cout<<endl;return ;}for(int i = p; i <= n - 1; i++){	if(sum + i <= n){	a[d] = i;dfs(d + 1, i, sum + i);}}
}
int main() 
{cin>>n;dfs(1, 1, 0);return 0;
}