题目描述

把一个正整数N表示成如下表达式的一系列正整数的和，叫做整数N（N≤40）的一个划分。

某个正整数N的不同表达式的个数称为整数N的分划数。编程输出所有的划分 。

输入格式

一个整数N。

输出格式

多行数据，前面多行输出划分情况，最后一行一个整数，即划分数。

样例

输入样例

4

输出样例：

5

提示

样例解释：

4=4;

4=3+1;

4=2+2;

4=2+1+1；

4=1+1+1+1

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[40],ans;
void dfs(int x,int y)
{
	if(y==0)
	{
		ans++;
		return ;
	}
	for(int i=a[x-1];i<=y;i++)
	{
		a[x]=i;
		dfs(x+1,y-i);
	}
}
int main()
{
	cin>>n;
	dfs(1,n);
	cout<<ans;
 }