简单的整数划分问题

点我去提交

题目描述
将正整数n 表示成一系列正整数之和，
n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。
正整数n 的这种表示称为正整数n 的划分。
正整数n 的不同的划分个数称为正整数n 的划分数。

Input

标准的输入包含若干组测试数据。每组测试数据是一个整数N(0 < N <= 50)。

Output

对于每组测试数据，输出N的划分数。

Sample Input

5

Sample Output

7

解题思路

这一题是不断使用深搜来寻找能够组成你输入数字的组成方式的个数

完整代码如下

#include<stdio.h>
int a,sum;
void dfs(int step,int x)
{if(step==a){sum++;return;}for(int k=x;k>=1;k--)if(step+k<=a)dfs(step+k,k);return;
}
int main()
{while(~scanf("%d",&a)){sum=0;dfs(0,a);printf("%d\n",sum);}return 0;
}