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

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
const int N=25,M=(1<<20);
int n,k,ans,a[N],vis[M];
map<int,vector<int>>H;
void dfs1(int x,int now,int sum){
	if(x==k+1){
		//cout<<sum<<"------------"<<now<<endl;
		H[sum].push_back(now);
	}else{
		dfs1(x+1,now,sum);
		dfs1(x+1,now|(1<<(x-1)),sum+a[x]);
		dfs1(x+1,now|(1<<(x-1)),sum-a[x]);
	}
	return;
}
void dfs2(int x,int now,int sum){
	if(x==n+1){
		//cout<<sum<<"ssssssssssss"<<now<<endl;
		for(auto v:H[-sum]){
			vis[(now<<(n/2))|v]=1;
		}
	}else{
		dfs2(x+1,now,sum);
		dfs2(x+1,now|(1<<(x-k-1)),sum+a[x]);
		dfs2(x+1,now|(1<<(x-k-1)),sum-a[x]);
	}
	return;
}
int main(){
	freopen("subsets.in","r",stdin);
	freopen("subsets.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
	}
	k=n/2;
	dfs1(1,0,0);
	dfs2(k+1,0,0);
	for(int i=1;i<(1<<n);i++){
		if(vis[i])ans++;
	}
	printf("%d\n",ans);
	return 0;
}