c++--study||O.o 深搜DFS(两种写法)

参考代码:

利用设置外部变量

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n,k; cin>>n>>k;
    long long res = 0;
     
    auto dfs = [&](auto&& dfs, int step, int n, int pre){
        if(n==0 && step==k){
            res++;
            return;
        }
        if(n==0 || step==k) return;
        for(int x=pre; x<=n; x++){
            dfs(dfs, step+1, n-x, x);
        }
    };
    dfs(dfs, 0, n, 1);
    cout << res;
    return 0;
}

利用返回值

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n,k; cin>>n>>k;
     
    auto dfs = [&](auto&& dfs, int step, int s, int pre)->long long{
        if(s+step<k) return 0; // 一个小剪枝
        if(s==0 && step==k) return 1;
        if(s==0 || step==k) return 0;
        long long ret = 0;
        for(int x=pre; x<=s; x++){
            ret += dfs(dfs, step+1, s-x, x);
        }
        return ret;
    };
    cout << dfs(dfs, 0, n, 1);
    return 0;
}