记录编号	606898	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4179.毛一琛	最终得分	100
用户昵称	梦那边的美好TT	是否通过	通过
代码语言	C++	运行时间	2.386 s
提交时间	2025-10-04 16:45:08	内存使用	51.81 MiB

#include<bits/stdc++.h>
#define N 2000001
using namespace std;
int n,a[21],ans[N],s,tot;
vector<int> v[N];
map<int,int> m;
void dfs1(int x,int sum,int now){
	if(x>n/2){
		if(m[sum]==0) m[sum]=++tot;
		v[m[sum]].push_back(now);
		return ;
	}
	dfs1(x+1,sum+a[x],now|(1<<(x-1)));
    dfs1(x+1,sum-a[x],now|(1<<(x-1)));
    dfs1(x+1,sum,now);
    return ;
}
void dfs2(int x,int sum,int now){
	if(x>n){
		if(m[sum]!=0) for(auto i:v[m[sum]]) ans[i|now]=1;
		return ;
	}
	dfs2(x+1,sum+a[x],now|(1<<(x-1)));
    dfs2(x+1,sum-a[x],now|(1<<(x-1)));
    dfs2(x+1,sum,now);
    return ;
} 
int main(){
    freopen("subsets.in","r",stdin);
    freopen("subsets.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	dfs1(1,0,0);
	dfs2(n/2+1,0,0);
	for(int i=1;i<=(1<<n);i++) s+=ans[i];
	cout<<s<<endl;
	return 0;
}