数的划分

题目描述
将整数n分成k份，且每份不能为空，任意两个方案不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5;
1，5，1;
5，1，1;
问有多少种不同的分法。
输入：n，k ( 6 < n ≤ 200，2 ≤ k ≤ 6 )
输出：一个整数，即不同的分法。
输入描述:
两个整数 n,k ( 6 < n ≤ 200， 2 ≤ k ≤ 6 )
输出描述:
1个整数，即不同的分法。
示例1
输入
复制
7 3
输出
复制
4

题目分析
1.实际上把n个数字填到k个方块里
2.利用升序法，维护一个left参数，对dfs进行优化，能够有效避免重复

#include<iostream>
using namespace std;
int arr[8] = {1};
int ans;
int n, k;
void dfs(int s,int left)
{
    if (s == k + 1)
    {
        ans++;
        return;
    }
    if (s == k)
    {
        if(left>=arr[s-1])
        {
            arr[s] = left;
            dfs(s + 1, 0);
        }
        return;
    }
    for (int i = arr[s - 1]; i <=left; i++)//选择范围应该比上个数字大 这样不能重复
        arr[s] = i;
        dfs(s + 1,left-i);
    }
}
int main()
{
    cin >> n >> k;
    dfs(1, n);
    cout << ans;
}