Partitioning a set of $N$ integers into two disjoint subsets with equal sums requires checking $3^N$ possible states, as each number can be placed in the first group, the second group, or excluded entirely. When $N \le 20$, a direct brute-force approach is computationally infeasible. By applying a meet-in-the-middle strategy, the array is divided into two halves, reducing the exponential complexity from $3^N$ to rough $3^{N/2}$.

Recursive Depth-First Search Implementation

Split the array into a left segment and a right segment. Recursively traverse the left segment, maintaining a cumulative sum difference (adding the value for the first group, subtracting for the second, or ignoring it) and a bitmask representing the included indices. Store these mappings from sum differences to their corresponding bitmasks in a hash map.

During the traversal of the right segment, calculaet its sum difference. If the negative of this sum exists in the left segment's map, it signifies that the included elements from both halves can be partitioned into two equal-weight groups. Merge the bitmasks from both halves using a bitwise OR operation and record the resulting configuration in a set to ensure distinct subset counts. The empty configuration (where no element are selected) is naturally excluded.

#include <iostream>
#include <vector>
#include <map>
#include <unordered_set>

using namespace std;

int n;
long long arr[25];
map<long long, vector<int>> leftMappings;
unordered_set<int> validCombinations;

void generateLeft(int pos, long long sumDiff, int bitmask) {
    if (pos > n / 2) {
        leftMappings[sumDiff].push_back(bitmask);
        return;
    }
    generateLeft(pos + 1, sumDiff + arr[pos], bitmask | (1 << (pos - 1)));
    generateLeft(pos + 1, sumDiff - arr[pos], bitmask | (1 << (pos - 1)));
    generateLeft(pos + 1, sumDiff, bitmask);
}

void generateRight(int pos, long long sumDiff, int bitmask) {
    if (pos > n) {
        if (leftMappings.count(-sumDiff)) {
            for (int leftMask : leftMappings[-sumDiff]) {
                validCombinations.insert(leftMask | bitmask);
            }
        }
        return;
    }
    generateRight(pos + 1, sumDiff + arr[pos], bitmask | (1 << (pos - 1)));
    generateRight(pos + 1, sumDiff - arr[pos], bitmask | (1 << (pos - 1)));
    generateRight(pos + 1, sumDiff, bitmask);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    
    generateLeft(1, 0, 0);
    generateRight(n / 2 + 1, 0, 0);
    
    int answer = 0;
    for (int mask : validCombinations) {
        if (mask != 0) answer++;
    }
    cout << answer << "\n";
    return 0;
}

Iterative Ternary State Compression

Instead of recursive branching, the three states (excluded, group A, group B) can be encoded as digits in a base-3 number. For each half, iterate through all possible ternary numbers up to $3^{len} - 1$. Decode each digit to determine the current element's assignment, updating the sum difference and building a binary bitmask that marks the included indices regardless of their group assignment.

Group the resulting bitmasks by their calculated sum differences for both halves. Iterate through the sums of the left half, checking if the opposing negative sum exists in the right half. When a match is found, combine the corresponding bitmasks. A set filters out duplicate combinations, and configurations where the merged bitmask equals zero are discarded to omit the empty subset.

#include <iostream>
#include <vector>
#include <map>
#include <unordered_set>

using namespace std;

int n;
long long vals[22];
int pow3[12];
unordered_set<int> finalMasks;

map<long long, vector<int>> enumerateHalf(int offset, int len) {
    map<long long, vector<int>> sums;
    for (int state = 0; state < pow3[len]; ++state) {
        long long sumDiff = 0;
        int mask = 0;
        
        for (int i = 0; i < len; ++i) {
            int digit = (state / pow3[i]) % 3;
            int bitPos = offset + i;
            
            if (digit == 1) {
                sumDiff += vals[bitPos];
                mask |= (1 << bitPos);
            } else if (digit == 2) {
                sumDiff -= vals[bitPos];
                mask |= (1 << bitPos);
            }
        }
        sums[sumDiff].push_back(mask);
    }
    return sums;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> vals[i];
    
    pow3[0] = 1;
    for (int i = 1; i <= 11; ++i) pow3[i] = pow3[i - 1] * 3;
    
    int size1 = n / 2;
    int size2 = n - size1;
    
    map<long long, vector<int>> leftPart = enumerateHalf(0, size1);
    map<long long, vector<int>> rightPart = enumerateHalf(size1, size2);
    
    for (const auto& [sum1, masks1] : leftPart) {
        if (rightPart.count(-sum1)) {
            for (int m1 : masks1) {
                for (int m2 : rightPart[-sum1]) {
                    if ((m1 | m2) != 0) {
                        finalMasks.insert(m1 | m2);
                    }
                }
            }
        }
    }
    
    cout << finalMasks.size() << "\n";
    return 0;
}