剪枝原则

• 正确性：保证不丢失正解的结果；
• 准确性：尽量剪去多余枝条；
• 高效性：降低时间复杂度的同时，提高判断操作本身的效率。

DFS优化技巧

• 优化搜索顺序：确定一个较优的搜索顺序，例如求最小值，就从最小值先搜索，效率或许更为优秀。
• 排除等效冗余：当多个枝条具有完全相同的结果的时候，只选择一个即可。
• 可行性剪枝：当前结果不可行，就不再继续搜索。
• 最优性剪枝：当前结果与已有结果相比，不是最优了，就不必继续搜索。
• 记忆化搜索(DP)：将当前位置的结果记录下来，以后再次搜索该位置结果的时候直接返回存储的结果。
• 奇偶性判断：提前确定奇数与偶数的情况下的不同状态，看能否提前处理。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
int n, k, ans;

void dfs(int u, int s, int c) {
    if (c >= k || s >= n) {
        if (c == k && s == n) ans++;
        return;
    }
    for (int i = u; i >= 1; i--) {
        dfs(i, s + i, c + 1);
    }
}
int main(int argc, char* argv[]) {
    cin >> n >> k;
    dfs(n, 0, 0);
    cout << ans;
    return 0;
}