题目描述
将整数 n 分成 k 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。
例如：n=7，k=3，下面三种分法被认为是相同的。
1,1,5;
1,5,1;
5,1,1.
问有多少种不同的分法。
输入格式
n,k （6<n≤200，2≤k≤6）
输出格式
1 个整数，即不同的分法。
输入输出样例
输入 #1复制
7 3
输出 #1复制
4
说明/提示
四种分法为：
1,1,5;
1,2,4;
1,3,3;
2,2,3.
【题目来源】
NOIP 2001 提高组第二题
#include<bits/stdc++.h>
using namespace std;int n,k;
int ans;
int sum;//保存已经搜索到的数的和void dfs(int x,int dep){if(dep==k-1){ //当深度达到 k-1 时就不用搜了 因为最后一个值已经确定了ans++;return;}sum+=x;for(int i=x;i<=(n-sum)/(k-dep);i++){ //i 的值应该大于等于他的上一个数，小于等于 剩余的数/剩余的数量（向下取整）dfs(i,dep+1);}sum-=x;//恢复原状态
}int main(){cin>>n>>k;for(int i=1;i<=n/k;i++){sum=0;//每次对一个新的数进行 dfs 之前，先清空 sumdfs(i,1);}cout<<ans<<endl;return 0;
} 
