Meet in the middle题解

与例题类似，也是分成左右两部分合并，区别是这里是问有多少钟方案使得子集加起来为 $x$ 。这个操作也具有结合率的性质，所以可以用meet in the middle方法。

此处我们使用unordered_map进行生成结果的存储，和vector类似，是另外一种实现方式。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, x;   // n <= 40
int t[45];
unordered_map<int,int> cnts;
ll ans;
 
int main() {
    scanf("%d %d", &n, &x);
    for (int i = 0; i < n; i++)
        scanf("%d", &t[i]);
    for (int bm = 0; bm < (1 << n/2); bm++) {
        int sum = 0;
        bool ok = true;
        for (int i = 0; i < n/2; i++) {
            if (bm & (1 << i)) {
                sum += t[i];
                if (sum > x) {
                    ok = false; break;
                }
            }
        }
        if (ok) cnts[sum]++;
    }
 
    for (int bm = 0; bm < (1 << (n-n/2)); bm++) {
        int sum = 0;
        bool ok = true;
        for (int i = 0; i < (n-n/2); i++) {
            if (bm & (1 << i)) {
                sum += t[i+n/2];
                if (sum > x) {
                    ok = false; break;
                }
            }
        }
        ans += cnts[x-sum];
    }
    printf("%lld", ans);
 
    return 0;
}