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

#include <iostream>
#include <map>
#include <vector>
using namespace std;

const int MAXN = 2e6 + 10;

int n;
int a[21];
int cnt;
map<int, int> mp;
vector<int> solution[MAXN];
int ans[MAXN];

void dfs1(int step, int sum, int choose) {
  if (step > n / 2) {
    if (!mp[sum]) mp[sum] = ++cnt;
    solution[mp[sum]].push_back(choose);
    return ;
  }
  dfs1(step + 1, sum + a[step], choose | (1 << (step - 1)));
  dfs1(step + 1, sum - a[step], choose | (1 << (step - 1)));
  dfs1(step + 1, sum, choose);
}

void dfs2(int step, int sum, int choose) {
  if (step > n) {
    if (mp[sum]) for (auto x : solution[mp[sum]]) ans[x | choose] = 1;
    return ;
  }
  dfs2(step + 1, sum + a[step], choose | (1 << (step - 1)));
  dfs2(step + 1, sum - a[step], choose | (1 << (step - 1)));
  dfs2(step + 1, sum, choose);
}

int main() {
  freopen("subsets.in", "r", stdin);
  freopen("subsets.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(false), cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];

  dfs1(1, 0, 0);
  dfs2(n / 2 + 1, 0, 0);

  int ans = 0;
  for (int i = 1; i <= (1 << n); ++i) ans += ::ans[i];
  cout << ans << endl;
  return 0;
}