记录编号	606944	评测结果	AAAAAAAAAAAATAAAAAAA
题目名称	4179.毛一琛	最终得分	95
用户昵称	李奇文	是否通过	未通过
代码语言	C++	运行时间	8.832 s
提交时间	2025-10-04 17:49:33	内存使用	233.50 MiB

#include<bits/stdc++.h>
#define re register
using namespace std;
const int N=1e8+5;
int a[25],n,ans,tot;
bool vis[N];
map<int,int> m;
vector<int>v[10000005];
void dfs1(re int k,re int res,re int hs){
	if(k==n/2+1){
		if(m.find(res)==m.end()) m[res]=++tot;
		v[m[res]].push_back(hs);
		return;
	}
	dfs1(k+1,res,hs);
	dfs1(k+1,res+a[k],hs|(1<<(k-1)));
	dfs1(k+1,res-a[k],hs|(1<<(k-1)));	
}
void dfs2(re int k,re int res,re int hs){
	if(k==n+1){
		if(m.find(res)!=m.end()){
			for(re int i=0;i<v[m[res]].size();++i){
				vis[v[m[res]][i]|hs]=1;
			}
		}
		return;
	}
	dfs2(k+1,res,hs);
	dfs2(k+1,res-a[k],hs|(1<<(k-1)));
	dfs2(k+1,res+a[k],hs|(1<<(k-1)));
}
int main(){
	freopen("subsets.in","r",stdin);
	freopen("subsets.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(re int i=1;i<=n;++i){
		cin>>a[i];
	}
	dfs1(1,0,0);
	dfs2(n/2+1,0,0);
	for(re int i=1;i<=(1<<n)-1;++i){
		ans+=vis[i];
	}
	cout<<ans<<"\n";
	return 0;
}