subsets(2018.10.16)

一句话题意：给你一个包含n个元素的集合，问有多少个非空子集，能划分成和相等的两份。(n<=20)

题解：对于这道题，我们很轻易可以列出\(O(3^n)\)的暴力，这是显然过不了的，观察这道题的性质可以发现我们显然可以查找左半边把值扔到hash表里，然后查找右半边的时候更新答案，这是显然正确的，因为我们对于hash表维护的的是两个集合的差值，所以不用担心每半边内部的情况会判不到。

#include<cstdio>

#include<algorithm>

using namespace std;

int now,n,h[1000011],nxt[1000011],a[1000011],B[1000011],A[1000011],nm[22],ans;

bool vis[10000011];

const int mod=1000007;

void ins(int x,int y)

{

    int k=abs(x)%mod;

    for(int i=h[k];i;i=nxt[i])

        if(A[i]==x&&B[i]==y)return ;

    ++now;nxt[now]=h[k];h[k]=now;A[now]=x;B[now]=y;

}

void get(int x,int y)

{

    int k=abs(x)%mod;

    for(int i=h[k];i;i=nxt[i])

        if(A[i]==x)vis[y+B[i]]=1;

}

void dfs2(int x,int y,int z)

{

    if(x==n+1)

    {

        get(y,z);

        return ;

    }

    dfs2(x+1,y+a[x-1],z+nm[x-1]);

    dfs2(x+1,y-a[x-1],z+nm[x-1]);

    dfs2(x+1,y,z);

}

void dfs1(int x,int y,int z)

{

    if(x==n/2+1)

    {

        ins(y,z);

        return ;

    }

    dfs1(x+1,y+a[x-1],z+nm[x-1]);

    dfs1(x+1,y-a[x-1],z+nm[x-1]);

    dfs1(x+1,y,z);

}

int main()

{

    scanf("%d",&n);

    nm[0]=1;

    for(int i=1;i<=21;i++)nm[i]=nm[i-1]<<1;

    for(int i=1;i<=n;i++)scanf("%d",&a[i-1]);

    dfs1(1,0,0);dfs2(n/2+1,0,0);

    for(int i=1;i<=(1<<n);i++)if(vis[i])ans++;

    printf("%d",ans);

}