警钟撅烂
讲一下搜索的剪枝
每一次搜索不需要都从1开始 而是从last
开始(即上一次搜索搜到且未结束的数)
因为函数没有结束 所以$ last \le n$
而且循环必须要建立在 目前遍历到的数加上之前的和$\le n$的前提下
Talk is easy. Show me your code.
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n, k, ans;
void dfs(int last, int num, int sum){
if (sum == k){ // 因为有可能凑不成这个数啊 所以这两个if要分开写
if (num == n) ans ++;
return;
}
for (int i = last; i + num <= n; i ++){
dfs(i, num + i, sum + 1);
}
}
int main(){
cin >> n >> k;
dfs(1, 0, 0);
cout << ans << endl;
return 0;
}