Count Equal-Size Equal-Total Splits

You are given n numbers, where n is even. Count the ways to split them into two groups of exactly n / 2 numbers each so that the two group totals are equal. Print the count.

A split is identified by WHICH POSITIONS go into the group, so two splits are different when they use a different set of positions, even if the values are equal. Each split is counted once for each of its two groups, which means a split into group X and group Y is counted both as X and as Y when both have size n / 2. Concretely: for the input 5 5, the answer is 2, because position 0 alone and position 1 alone are two different qualifying groups.

## What most people try first

Enumerate the groups of size n / 2. There are n choose n/2 of them, which at n = 40 is 137846528820. Hopeless.

A table indexed by the total also fails: the numbers reach 10^9 so the totals reach 4 * 10^10, and no array of that length exists.

## The quick check that comes first

If the overall total is odd then no equal split exists at any size, so the answer is 0 and no search is needed. Doing this first also saves you from an integer division that would silently floor.

## Halve the list, and key on the pair

Split into halves of about twenty and enumerate each half, recording for every part its total and its size. Both quantities add across the split: a qualifying group has total exactly half the overall total and size exactly n / 2, so its left part and right part must have totals adding to half the overall total and sizes adding to n / 2.

So build a map from the PAIR (total, size) to how many left parts have it. Then for each right part of total s and size c, add the map's count for the pair (half the total minus s, n / 2 minus c).

## Why the key must be the pair

Keying on the total alone counts groups of every size that reach half the total, which answers a different and larger question. Keying on the size alone is obviously useless. Both constraints bind at once, and a pair key enforces both for the same cost, because the map holds the same number of entries either way.

## The boundary that breaks a careless implementation

A negative required size. A right part using more than n / 2 numbers makes n / 2 minus c negative, and the lookup must MISS rather than be clamped to zero, because clamping to zero would wrongly admit the empty left part.

The other is the counting convention. Because both groups have the same size, each split is found twice, once from each side. The statement pins the answer to count qualifying GROUPS, which is the convention under which 5 5 gives 2, so no halving is applied. If you want the number of unordered splits, it is this answer divided by two, but that is not what is asked here and the statement says so to remove the ambiguity.

## Overflow

The count reaches 40 choose 20, which is 137846528820, so the count needs 64 bits. Totals reach 4 * 10^10, which also needs 64 bits.

## Cost

2^(n/2) to build the map and 2^(n/2) lookups.

## Worked example

``` numbers 3 1 4 2 total 10, so each group must total 5 and hold 2 numbers

left half 3 1 parts as (total, size) (0,0) (3,1) (1,1) (4,2) map: {(0,0):1, (3,1):1, (1,1):1, (4,2):1}

right half 4 2 parts as (total, size) (0,0) (4,1) (2,1) (6,2)

r = (0,0) need (5,2) absent adds 0 r = (4,1) need (1,1) count 1 adds 1 group 4 and 1 r = (2,1) need (3,1) count 1 adds 1 group 2 and 3 r = (6,2) need (-1,0) absent adds 0

answer 2 ```

### Constraints - 2 <= n <= 40, and n is even - 0 <= each number <= 10^9 - The count reaches 40 choose 20, which is 137846528820, so the count needs a 64-bit type as well as the totals.