记录编号	606858	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4179.毛一琛	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	2.290 s
提交时间	2025-10-04 15:48:20	内存使用	55.32 MiB

 
#include <cstdio>
#include <iostream>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
const int N = 21;
 
int n;
int n1;
int n2;
int nums[N];
int cc;
unordered_map<int, int> ma;
vector<int> cons[1 << N];
int ans[1 << N];
int res;

void dfs (int now, int last, int con, int sum) {
	if (now > last) {
		if (last == n1) {
			if (!ma.count(sum)) {
				cc++;
				ma[sum] = cc;
			}
			cons[ma[sum]].push_back(con);
		}
		else {
			for (auto c : cons[ma[sum]]) {
				ans[con | c] = 1;
			}
		}
		return;
	}
	dfs (now + 1, last, con, sum);
	dfs (now + 1, last, con | (1 << now), sum + nums[now]);
	dfs (now + 1, last, con | (1 << now), sum - nums[now]);
}

int main () {
    
    freopen ("subsets.in", "r", stdin);
    freopen ("subsets.out", "w", stdout);
    
    cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> nums[i];
	}
    n1 = n / 2;

	dfs (1, n1, 0, 0);
	dfs (n1 + 1, n, 0, 0);

	for (int i = 1; i < (1 << (n + 1)); i++) {
		if (ans[i]) {
			res++;
		}
	}

	cout << res << endl;
    
    return 0;
}