题解 | #神奇的口袋#

#include <bits/stdc++.h>
#include <variant>
#include <vector>
using namespace std;
//组合问题
int res = 0;
vector<bool> used(21, 0);
void dfs(int value, int index, vector<int> v) {
    if (value == 40) {//收集结果
        res++;
        return;
    }
    if (value > 40) return ;//剪枝---value>40就不要继续了
    if (index == v.size()) return ;//越界了就不要继续了
    for (int i = index; i < v.size(); i++) {
        //需要index来记录下一层递归，搜索的起始位置。index 就是防止出现重复的组合。
        dfs(value + v[i], i + 1, v);
    }
}
int main() {
    int n;
    while (cin >> n) {
        int data;
        vector<int> v;
        while (n--) {
            cin >> data;
            v.push_back(data);
        }
        //以上是处理输入
        dfs(0, 0, v);
        cout << res << endl;
    }
}
// 64 位输出请用 printf("%lld")