Description：

给 $n$ 个数，从中任意选出一些数，使这些数能分成和相等的两组，求有多少种选数的方案。

$1\leqslant n\leqslant 20$

Solution：

$n$ 只有 $20$ ，那就可以折半搜索，先 $3^{10}$ 搜出来前半部分，再搜出来后半部分，然后一个从大到小一个从小到大排序，双指针扫一下，注意如果有很多相同的值要扫很多遍，去重可以把所有选择方案状压一下，用一个 $vis$ 记录。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 22

int v[MAXN];

struct state

{

	int t,x;

}lef[200000],rig[200000];

int totlef = 0,totrig = 0;

bool cmp_x_lth(state a,state b){return a.x < b.x;}

bool cmp_x_htl(state a,state b){return a.x > b.x;}

void dfs1(int pos,int sum,int sta)

{

	if(pos > n / 2)

	{

		lef[++totlef] = (state){sta,sum};

		return;

	}

	dfs1(pos + 1,sum,sta);

	dfs1(pos + 1,sum + v[pos],sta |= (1 << (pos - 1)));

	dfs1(pos + 1,sum - v[pos],sta |= (1 << (pos - 1)));

	return;

}

void dfs2(int pos,int sum,int sta)

{

	if(pos > n)

	{

		rig[++totrig] = (state){sta,sum};

		return;

	}

	dfs2(pos + 1,sum,sta);

	dfs2(pos + 1,sum + v[pos],sta |= (1 << (pos - 1)));

	dfs2(pos + 1,sum - v[pos],sta |= (1 << (pos - 1)));

	return;

}

bool vis[1 << MAXN];

int ans = 0;

int main()

{

	scanf("%d",&n);

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

	dfs1(1,0,0);

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

	sort(lef + 1,lef + 1 + totlef,cmp_x_lth);

	sort(rig + 1,rig + 1 + totrig,cmp_x_htl);

	memset(vis,false,sizeof(vis));

	int last;

	for(int i = 1,j = 1;i <= totlef;++i)

	{

		while(j <= totrig && lef[i].x + rig[j].x > 0)++j;

		if(i != 1 && lef[i].x == lef[i - 1].x)j = last;

		last = j;

		while(j <= totrig && lef[i].x + rig[j].x == 0)

		{

			if(!vis[lef[i].t | rig[j].t])

			{

				++ans;

				vis[lef[i].t | rig[j].t] = true;

			}

			++j;

		}

	}

	cout << ans - 1 << endl;

	return 0;

}