【算法】折半搜索+数学计数
【题意】给定n个数(n<=20)，定义一种方案为选择若干个数，这些数可以分成两个和相等的集合（不同划分方式算一种），求方案数（数字不同即方案不同）。
【题解】
考虑直接枚举集合的子集，再枚举子集的子集(划分方式)，相当于将子集看成天平，枚举子集一些数置左，剩余数置右，则每个数有三种可能：不选，置左，置右。
由此可知，直接枚举集合子集的子集复杂度是O(3^n)。
考虑将总集划分成两半，则枚举一半的复杂度为O(3^(n/2))。
得到两半都如何合并？
如果相同集合不同划分方式算多种的话，可以将两半都unique，然后枚举一半的所有天平，在另一半二分找到相等天平，统计方案，复杂度O(3^(n/2)*log(3^(n/2))。
但是题目要求相同集合只算一次，如果仍然用上述方法则不能unique，因为相同集合只算一次，可以将方案标记到vis[]，最后一次统计。但是没有unique的话二分就没有意义（如果全部数字相同仍需要全部扫描），复杂度O(3^n)，显然超时。
考虑另一种方法，将一组数拿过去比较，两边两指针扫描，相等的标记到vis[]。这样有一个问题，就是左边拿来比较的数字不能有相同的数字，否则复杂度又不对了。
我们将左边的天平按选择的方案划分，即相同方案的一起处理，相同方案内相同的数字就可以舍去，不同的数字就两指针扫一遍，这样保证复杂度O(6^(n/2))。
总复杂度O(6^(n/2))。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct left{int v,from;}l[120010]; struct right{int v,s;}r[120010]; int n,first[2100],n0,ltot=0,rtot=0,a[30],m,q[120010]; bool vis[2200010]; void dfsl(int dep,int v,int s){ if(dep==n0){ltot++;l[ltot].v=v;l[ltot].from=first[s];first[s]=ltot;} else{ dfsl(dep+1,v,s); dfsl(dep+1,v+a[dep],s|(1<<dep)); dfsl(dep+1,v-a[dep],s|(1<<dep)); } } void dfsr(int dep,int v,int s){ if(dep==n){rtot++;r[rtot].v=v;r[rtot].s=s;} else{ dfsr(dep+1,v,s); dfsr(dep+1,v+a[dep],s|(1<<dep)); dfsr(dep+1,v-a[dep],s|(1<<dep)); } } bool cmp(right a,right b){return a.v<b.v;} int main() { scanf("%d",&n); for(int i=0;i<n;i++)scanf("%d",&a[i]); n0=(n+1)/2; dfsl(0,0,0);//0~n0-1 dfsr(n0,0,0);//n0~n-1 sort(r+1,r+rtot+1,cmp); for(int i=0;i<(1<<n0);i++){ m=0; for(int j=first[i];j;j=l[j].from)q[++m]=l[j].v; sort(q+1,q+m+1); int k=1; for(int j=1;j<=rtot;j++){ while(k<=m&&q[k]<r[j].v)k++; if(k>m)break; if(q[k]==r[j].v)vis[r[j].s|i]=1; } } int ans=0; for(int i=1;i<(1<<n);i++){if(vis[i])ans++;}//细节：必须选数 printf("%d",ans); return 0; }