整数的划分 NC16695

原题链接

思路

本题目数据量较弱，所以可以考虑直接用dfs

代码

#include<iostream>

using namespace std;

int ans;

void dfs(int n, int d, int k){
    if(k == 0){
        if(n == 0) ans++;
        return;
    }
    
    for(int i = d; i <= n; i++)
        dfs(n - i, i, k - 1);
}
//保证不重复，是因为保证了整数的划分方案内部内容是递增的
int main(){
    int n, k;
    cin >> n >> k;
    dfs(n,1,k);
    cout << ans;
    return 0;
}