子集和(Subset Sum) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int mid = n / 2;
    int n1 = mid, n2 = n - mid;
    vector<long long> s1(1 << n1, 0), s2(1 << n2, 0);
    for (int i = 0; i < n1; ++i) {
        int bit = 1 << i;
        for (int mask = 0; mask < bit; ++mask) {
            s1[mask | bit] = s1[mask] + a[i];
        }
    }
    for (int i = 0; i < n2; ++i) {
        int bit = 1 << i;
        for (int mask = 0; mask < bit; ++mask) {
            s2[mask | bit] = s2[mask] + a[mid + i];
        }
    }
    sort(s2.begin(), s2.end());
    long long ans = 0;
    for (long long x : s1) {
        auto it = upper_bound(s2.begin(), s2.end(), -x);
        ans += (s2.end() - it);
    }
    cout << ans << "\n";
    return 0;
}