题解 | #神奇的口袋#

深度优先搜索，搜索状态为（累加和，当前位置），沿下标递增顺序搜索，保证结果中没有重复的计数

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int num = 0;
int n;
int a[20];
void dfs(int sum, int pos) {
    if (sum == 40) {
        num++;
        return;
    } else if (sum > 40) return;
    else {
        for (int i = pos; i < n; i++)
            dfs(sum + a[i], i+ 1);//沿下标递增方向搜索，保证不走回头路
    }

}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    dfs(0, 0);
    cout << num<< endl;
    return 0;
}

// 64 位输出请用 printf("%lld")