题意

有可重集$S$, 求它的非空子集$X$的个数, 满足: $X=A\cup B, A\cup B=\emptyset, \Sigma A_i=\Sigma B_i$. 其中$|S| \leq 20$, $S_i \leq 10^8$.

思路

考虑使用Meet in The Middle思路, 时间复杂度是朴素算法的平方根. 一般地, 把集合$S$分为两部分来搜索, 于是对于每个元素就有了三种分支: 不选, 选入左部分 和 选入右部分. 最后进行两部分的合并操作, 关键在于去重.

代码

const int N = 30;
int a[N];
bitset<1<<10> vis[1<<10];
unordered_map<int, bitset<1<<10> > mp;
struct Node{
    int dep, sum, sta;
};
int main(){
    int n, mid;
    cin>>n, mid = n>>1;
    for(int i=0;i<n;i++) cin>>a[i];
    stable_sort(a, a+n);
    queue<Node> q;
    q.push(Node{0, 0, 0});
    while(!q.empty()){
        int x =q.front().dep, y=q.front().sum, z=q.front().sta;
        q.pop();
        if(x==mid) {
            mp[y].set(z);
            continue;
        }
        q.push(Node{x+1, y, z});
        q.push(Node{x+1, y+a[x], z|(1<<x)});
        q.push(Node{x+1, y-a[x], z|(1<<x)});
    }
    q.push(Node{mid, 0, 0});
    int ans=0;
    while(!q.empty()){
        int x =q.front().dep, y=q.front().sum, z=q.front().sta;
        q.pop();
        if(x==n){
            if(mp.count(y)) {
                bitset<1<<10> tmp(mp[y]);
                tmp &=~vis[z], ans+=tmp.count(), vis[z]|=tmp;
            }
            continue;
        }
        q.push(Node{x+1, y, z});
        q.push(Node{x+1, y+a[x], z|(1<<(x-mid))});
        q.push(Node{x+1, y-a[x], z|(1<<(x-mid))});
    }
    cout<<ans-1<<endl;
}