考虑枚举 \(3^n\) 种情况，用三进制数表示。
对于每一位，\(0\) 表示不放，\(1\) 表示放入第一个集合，\(2\) 表示放入第二个集合。
这样显然会 TLE。考虑 meet in the middle。
考虑枚举前 \(3^{\left\lfloor\frac{n}{2}\right\rfloor}\) 种情况，开一个数组 / map 处理出所有可能的情况。
随后枚举后 \(3^{n-\left\lfloor\frac{n}{2}\right\rfloor}\) 种情况，和前面处理出的答案合并。
考虑如何合并。设前半段的第一个集合和为 \(a\)，第二个集合和为 \(b\)；后半段的第一个集合为 \(a'\)，第二个集合和为 \(b'\)，则有 \(a+a'=b+b'\)。
移项有 \(a-b=b'-a'\)，那么只要将答案用差为索引记录即可。
但是我们会发现一个情况，就是第一个集合和第二个集合只是我们规定的顺序，本质上它是无序对；除此之外，你不可以选两个空集。那么答案就是 \(\dfrac{ans-1}{2}\) 了吗？
其实不是。
看题目，发现要求选数的方案而非具体的安排方案，例如：
3 3 3 3
对于这四个数，分段为 3 3/3 3，前半段和后半段内共可以组成 \(2\) 个合法答案。
你会发现，\(a_1+a_2=a_3+a_4\) 本质上和 \(a_1+a_3=a_2+a_4\) 是一种选数方案。
考虑在枚举状态时加入选数的状态，用二进制 \(0/1\) 来表示。
开一个数组记录是否计算过一种方案的答案即可。
复杂度是 \(O(3^{\left\lfloor\frac{n}{2}\right\rfloor}\times2^{\left\lfloor\frac{n}{2}\right\rfloor})\) 即 \(O(6^{\left\lfloor\frac{n}{2}\right\rfloor})\) 的。\(3\) 为枚举集合分布，\(2\) 为记录的选数方案。
#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 20;
unordered_map <int, int> id; bool kk[N];
int n, idx, a[N]; vector <int> kel[N];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i];
int mid = n >> 1, lim = 1, res = 0; for (int i = 1; i <= mid; ++i) lim *= 3;
for (int s = 0; s < lim; ++s) {
int tmp = s, sum = 0, sta = 0;
for (int cnt = 1; cnt <= mid; ++cnt, sta = tmp % 3? (sta << 1 | 1) : (sta << 1), tmp /= 3)
if ((tmp % 3) & 1) sum += a[cnt]; else if (tmp % 3) sum -= a[cnt];
if (!id[sum]) id[sum] = ++idx;
kel[id[sum]].emplace_back(sta);
}
int lst = mid; mid = n - mid, lim = 1;
for (int i = 1; i <= mid; ++i) lim *= 3;
for (int s = 0; s < lim; ++s) {
int tmp = s, sum = 0, sta = 0;
for (int cnt = 1; cnt <= mid; ++cnt, sta = tmp % 3? (sta << 1 | 1) : (sta << 1), tmp /= 3)
if ((tmp % 3) & 1) sum -= a[cnt + lst]; else if (tmp % 3) sum += a[cnt + lst];
int curid = id[sum]; if (!curid) continue;
for (auto dk: kel[curid]) {
if (!((dk << mid) + sta)) continue;
if (kk[(dk << mid) | sta]) continue;
kk[(dk << mid) | sta] = true, ++res;
}
}
cout << res << endl;
return 0;
}