记录编号	606909	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4179.毛一琛	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	2.405 s
提交时间	2025-10-04 16:56:01	内存使用	51.99 MiB

#include <bits/stdc++.h>
using namespace std;

int n,N,a[21],ans[2000001],s,tot;
vector<int> p[2000001];
map<int,int> b;

void dfs1(int x,int sum,int now){
	if(x>N){
		if(b[sum]==0)b[sum]=++tot;
		p[b[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);
} 

void dfs2(int x,int sum,int now){
	if(x>n){ 
		int t=b[sum];
		if(t!=0)  for(int i=0;i<p[t].size();i++)  ans[p[t][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);
} 

int main(){
	freopen("subsets.in","r",stdin);
	freopen("subsets.out","w",stdout); 
	scanf("%d",&n); 
	N=n/2;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	dfs1(1,0,0);
	dfs2(N+1,0,0);
	for(int i=1;i<=(1<<n);i++){	
		s+=ans[i];
	}
	printf("%d",s);
}