题意

给出$n$个数，从中选出一些，求选出的数能分成相等的两份的方案数

数据范围：$2 \le n \le 20$

题解

对于每个元素，无非$3$种状态：

• $0$ 不选
• $-1$ 左
• $1$ 右

但直接搜索复杂度达到$O(3^n)$
考虑折半搜索
将组合二进制压缩，前半搜索记录下可能的$sum$，后半搜索从前半中找到相等的$sum$（其实是找$-sum$，但是是等价的），则此种选择方案成立
由于$sum$较大，需要离散化（不必排序）

注： 由于map常数较大，可以开启O2优化或考虑使用排序或hash/unordered_map

代码：

#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
const int N=20;
int n,tot,cnt,ans;
int a[N+1];
map<int,int> M;
vector<int> s[(1<<N)+1];
bool vis[(1<<N)+1];
void dfs1(int x,int sum,int stt){
    if(x>=tot){
        if(!M.count(sum))
            M[sum]=++cnt;
        s[M[sum]].push_back(stt);
        return ;
    }
    dfs1(x+1,sum,stt);
    dfs1(x+1,sum-a[x],stt|(1<<x));
    dfs1(x+1,sum+a[x],stt|(1<<x));
}
void dfs2(int x,int sum,int stt){
    if(x>=n){
        if(M.count(sum)){
            int t=M[sum];
            for(int i=0;i<s[t].size();i++)
                vis[s[t][i]|stt]=1;
        }
        return ;
    }
    dfs2(x+1,sum,stt);
    dfs2(x+1,sum-a[x],stt|(1<<x));
    dfs2(x+1,sum+a[x],stt|(1<<x));
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    tot=n>>1;
    dfs1(0,0,0);
    dfs2(tot,0,0);
    tot=1<<n;
    for(int i=1;i<tot;i++)
        ans+=vis[i];
    printf("%d",ans);
    return 0;
}