题面：

题解：

对于任意一个数，它要么属于集合A，要么属于集合B，要么不选它。对应以上三种情况设置三个系数1、-1、0，于是将题目转化

为找出两个集合和为0，将这两个集合合并不重复的为一种答案。考虑折半搜索。搜出前一半和后一半，用哈希表和状态压缩记录

和去重，然后统计答案即可。

时间复杂度为O(6^(N/2))。

代码：

1 #include
      
        2 using namespace std; 3 const int maxn=25,MOD=230203,max_num=6e4; 4 int N,M[maxn],num=0,ans=0,nx[max_num],hd[MOD+50]; 5 int Tmp[max_num],Sum[max_num],hf,ps; 6 bool vis[1050][1050]; 7 inline void Insert(int tmp,int sum){ 8     ps=(sum%MOD+MOD)%MOD; 9     for(int i=hd[ps];i;i=nx[i])10         if(Tmp[i]==tmp && Sum[i]==sum) return;//11     nx[++num]=hd[ps];12     Tmp[num]=tmp;13     Sum[num]=sum;14     hd[ps]=num;15     return;16 }17 inline int Find(int tmp,int sum){18     ps=(sum%MOD+MOD)%MOD;19     int ans=0;20     for(int i=hd[ps];i;i=nx[i])21         if(Sum[i]==sum && vis[Tmp[i]][tmp]==0){22             vis[Tmp[i]][tmp]=1;23             ans++;24         }25     return ans;26 }27 inline void Dfs1(int tp,int sum,int tmp){28     if(tp>hf){29         Insert(tmp,sum);30         return;31     }32     Dfs1(tp+1,sum+M[tp],tmp<<1|1);33     Dfs1(tp+1,sum-M[tp],tmp<<1|1);34     Dfs1(tp+1,sum,tmp<<1);35     return;36 }37 inline void Dfs2(int tp,int sum,int tmp){38     if(tp>N){39         ans+=Find(tmp,-sum);40         return;41     }42     Dfs2(tp+1,sum+M[tp],tmp<<1|1);43     Dfs2(tp+1,sum-M[tp],tmp<<1|1);44     Dfs2(tp+1,sum,tmp<<1);45     return;46 }47 int main(){48     scanf("%d",&N);49     hf=N>>1;50     for(int i=1;i<=N;i++) scanf("%d",&M[i]);51     Dfs1(1,0,0);52     Dfs2(hf+1,0,0);53     printf("%d\n",ans-1);54     return 0;55 }
      

 

---

By:AlenaNuna