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

#include <bits/stdc++.h>
using namespace std;
int n, vis[1 << 21];
int a[1001], ans, idx;
map<int, int> m;
vector<int> g[1 << 21];
void dfs(int step, int sum, int state){
	if (step >= n / 2){
		if (!m.count(sum))m[sum] = ++idx;
		g[m[sum]].push_back(state);
	}else{
		dfs(step + 1, sum, state);
		dfs(step + 1, sum + a[step], state | (1 << step));
		dfs(step + 1, sum - a[step], state | (1 << step));
	}
}
void dfs2(int step, int sum, int state){
	if (step >= n){
		if (m.count(sum)){
			int t = m[sum];
			for (int i = 0; i < g[t].size(); i++){
				vis[g[t][i] | state] = 1;
			}
		}
	}else{
		dfs2(step + 1, sum, state);
		dfs2(step + 1, sum - a[step], state | (1 << step));
		dfs2(step + 1, sum + a[step], state | (1 << step));
	}
}
int main(){
	freopen("subsets.in", "r", stdin);
	freopen("subsets.out", "w", stdout);
	cin >> n;
	for (int i = 0; i < n; i ++) cin >> a[i];
	dfs(0, 0, 0);
	dfs2(n / 2, 0, 0);
	for (int i = 1; i < (1 << n); i++){
		if (vis[i]){
			ans++;
		}
	}
	cout << ans << '\n';
	return 0;
}