题解 | #[NOIP2001]数的划分#

[NOIP2001]数的划分

#include <iostream>

using namespace std;

int n, k, cnt;

void dfs(int u, int s, int sum)//当前分成u份 上一个选择的数是s 当前总和是sum
{
    if(u > k) //只要满足u>k的条件就应该进入当前判断，不论是否sum==n都应该return
    {
        if(sum == n) cnt ++;
        return ;
    }
    
    for(int i = s; i <= n - sum; i ++)
        dfs(u + 1, i, sum + i);
}

int main()
{
    cin >> n >> k;
    dfs(1, 1, 0);
    cout << cnt ;
    
    return 0;
}