Split Into Two Equal-Size Groups
You are given n numbers, where n is even. Split them into two groups of EXACTLY n / 2 numbers each, so that every number lands in one group. Print the smallest possible difference between the two group totals.
The difference is reported as a non-negative amount, so it does not matter which group you call first.
## What most people try first
Try every split. There are n choose n/2 of them, which at n = 40 is 137846528820, about 1.4 * 10^11. Hopeless.
The second attempt is to solve this as the ordinary closest-split problem and hope the sizes come out even. They do not, and it is worth seeing a case rather than taking it on trust. On 1 2 3 100, whose total is 106, the best unconstrained split is 100 against 1 2 3, giving 100 and 6, a difference of 94. That is one number against three and therefore illegal here. The best legal two-against-two split is 1 100 against 2 3, giving 101 and 5, a difference of 96.
So the unconstrained optimum is not merely narrowed by the size rule, it is DISCARDED by it. A solution that finds the unconstrained best and then checks the sizes has already thrown the answer away. The size has to be carried through the whole search.
A table indexed by the total cannot be built either: the numbers reach 10^9 and there are forty of them, so the totals reach 4 * 10^10.
## Reduce the split to one number, as before
If one group has total p then the other has total minus p, so the difference is the absolute value of total minus twice p. You want p as close to half the total as possible, subject to p being reachable by exactly n / 2 of the numbers.
Here is the part that is new, and it is the same idea that any second constraint forces.
In the plain version of this technique you sort one half's totals and binary search the other. You cannot do that here, because a total on its own is no longer enough to know whether a pairing is legal: you also need to know how many items produced it. Sort the totals together and you have thrown that away, so the search happily returns a partner that uses the wrong number of items.
The fix is to BUCKET the half by item count. Build one sorted list of totals per count. Then a right half using c items looks only in the bucket for the count it actually needs, and inside that bucket every entry uses the same number of items, so the count rule is already satisfied and an ordinary nearest-value search over totals becomes valid again.
## Why it is correct
Every legal split has exactly one left part and one right part, and the two part sizes add to n / 2 just as the two part totals add to p. So for each right part of size c, the legal left partners are precisely the contents of the bucket for size n / 2 minus c, and searching that bucket for the total nearest to what is still needed considers every legal partner and nothing else.
## The boundary that breaks a careless implementation
A bucket that does not exist. If the right part already uses more than n / 2 items, the required left size is negative and there is no bucket, so that right part must be skipped rather than looked up. And the left half only has about n / 2 items in it, so a required size larger than that has no bucket either.
The second is the same floor problem as the unconstrained version: half of an odd total is not an integer, so after the binary search you must examine the neighbouring entries on both sides, not just the one below.
## Overflow
Totals reach 4 * 10^10 and twice the total reaches 8 * 10^10, both far past the 32-bit signed limit of 2147483647, so every total and the doubling need 64 bits. In JavaScript the doubling must not be written as a shift, because a shift truncates to 32 bits.
## Cost
2^(n/2) to enumerate each half, a sort per bucket, and one search per right part. A few million steps at n = 40.
## Worked example
``` numbers 3 1 4 2 total 10, so each group takes 2 numbers and ideally totals 5
left half 3 1 buckets by size size 0: 0 size 1: 1 3 size 2: 4
right half 4 2 parts as (total, size) (0,0) (4,1) (2,1) (6,2)
r = (0,0) need size 2 bucket 4 p = 4 difference |10 - 8| = 2 r = (4,1) need size 1 bucket 1 3 nearest to 1 is 1 -> p = 5 difference 0 r = (2,1) need size 1 bucket 1 3 nearest to 3 is 3 -> p = 5 difference 0 r = (6,2) need size 0 bucket 0 p = 6 difference 2
answer 0 ```
### Constraints - 2 <= n <= 40, and n is even - 0 <= each number <= 10^9 - Totals reach 4 * 10^10 and the doubling reaches 8 * 10^10, so a 64-bit type is required throughout.