题目描述

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。

当n=7共14种拆分方法：

7=1+1+1+1+1+1+1

7=1+1+1+1+1+2

7=1+1+1+1+3

7=1+1+1+2+2

7=1+1+1+4

7=1+1+2+3

7=1+1+5

7=1+2+2+2

7=1+2+4

7=1+3+3

7=1+6

7=2+2+3

7=2+5

7=3+4

输入

输入自然数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

思路：

        通过题目描述的样例：

7=1+1+1+1+3

7=1+1+1+2+2

可以发现最后每位数都要大于等于前一位数

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int N = 1e6;

int n;
int a[N]={0};
int s=0;
void ans(int step){
	for(int i=1;i<n;i++){
		if(s+i<n && i>=a[step-1]){//要求不小于前一位数
			a[step]=i;
			s+=i;
			ans(step+1);
			s-=i;
		}
		else if(s+i==n && i>=a[step-1]){//要求不小于前一位数，并且加起来等于n
			for(int j=1;j<step;j++){
				cout<<a[j]<<'+';
			}
			cout<<i<<endl;
			return;
		}
	}
}
int main(){
	cin>>n;
	ans(1);
	return 0;
}