WA 43分

思路meet in the middle：a表示当前第一个集合里面的和，b表示当前第二个集合里面的和，最后拿一个map统计一下差值，这样我们第二次搜索时，用相反的差值来更新ans，时间复杂度O(3 ^ 10 * log) code:

#include<cstdio>
#include<iostream>
#include<map>
#define ll long long
#define MAXM 30
using namespace std;

int n;

ll c[MAXM],ans;

map<ll,int>num;

void dfs1(int pos,ll a,ll b)
{
	if(pos == n / 2 + 1)
	{
		if(a == 0 && b == 0)return;
		num[a - b]++;
		return;
	}
	dfs1(pos + 1,a + c[pos],b);
	dfs1(pos + 1,a,b + c[pos]);
	dfs1(pos + 1,a,b);
}

void dfs2(int pos,ll a,ll b)
{
	if(pos == n + 1)
	{
		//cout << b - a << ' ' << num[b - a] << endl;
		ans += num[b - a];
		return;
	}
	dfs2(pos + 1,a + c[pos],b);
	dfs2(pos + 1,a,b + c[pos]);
	dfs2(pos + 1,a,b);
}

int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;i += 1)
		scanf("%lld",&c[i]);
	dfs1(1,0,0);
	dfs2(n / 2 + 1,0,0);
	printf("%lld\n",ans / 2);
	return 0;
}