记录编号	606852	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4179.毛一琛	最终得分	100
用户昵称	汐汐很希希	是否通过	通过
代码语言	C++	运行时间	2.367 s
提交时间	2025-10-04 15:29:09	内存使用	53.15 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=25;
const int M=1048576;
int n,sum=0,tot;
ll a[N],ans[M*2+10];
vector<int> p[2000001];
map<int,int> b;
void dfs1(int x,int sum,int now)
{
	if(x>n/2){
		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);
    
    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++) sum+=ans[i];
	cout<<sum<<endl; 
    return 0;
}