传送门
题意:给n个数，从中任意选出一些数，使这些数能分成和相等的两组,求有多少种选数的方案。(n<=20)
每个数有不选,加入左边集合,加入右边集合三种可能,3^20超时,考虑二分搜索.
将两个集合的得到的可能结果用双指针遍历,第一个指针在遇到相同的数时需要重置指针二为第一次遇到该数的位置
增加一个state记录选过哪些数,避免重复记录集合
最后减1去掉全空集合
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1<<22;
int c[maxn];
struct node
{int x;int state;
}a[maxn],b[maxn];
bool vis[maxn];
int n, cnt1,cnt2;
int maxdep;
void dfs(int dep,int now, int state, bool flag) {if(dep == maxdep){if(flag){a[++cnt1].x=now;a[cnt1].state=state;}else {b[++cnt2].x=now;b[cnt2].state = state;}return;}dfs(dep+1,now+c[dep],state+(1<<(dep-1)),flag);dfs(dep+1,now-c[dep],state+(1<<(dep-1)),flag);dfs(dep+1,now,state,flag);
}
int main()
{while(cin>>n){for(int i=1;i<=n;i++)scanf("%d",&c[i]);maxdep = n/2+1;dfs(1,0,0,1);maxdep = n+1;dfs(n/2+1,0,0,0);sort(a+1,a+cnt1+1,[](node a, node b){return a.x<b.x;});sort(b+1,b+cnt2+1,[](node a, node b){return a.x>b.x;});int l=1,r=1;ll ans=0;while(l<=cnt1&&r<=cnt2){while(a[l].x+b[r].x>0&&r<=cnt2)r++;int pos =r;while(r<=cnt2&&a[l].x+b[r].x==0){if(!vis[a[l].state|b[r].state])vis[a[l].state|b[r].state]=1,ans++;r++;}if(l<cnt1&&a[l].x==a[l+1].x)r=pos;l++;}cout<<ans-1<<endl;}
}