Split Into Two Closest Groups
You are given n numbers. Split all of them into two groups so that every number lands in exactly one group. Either group may be left empty. 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 2^n of them and at n = 40 that is about 10^12, too slow.
The next instinct is greedy: sort the numbers largest first and drop each one into whichever group is currently behind. That is a real algorithm, it is often close, and it is not optimal. It is worth seeing it fail on a tiny input rather than trusting it.
On 10 20 30 greedy puts 30 in the first group, then 20 in the second, then 10 in the second, giving 30 against 30. Difference 0, which is right.
On 8 7 6 5 4 greedy puts 8 in the first group, 7 in the second, 6 in the second (now 8 against 13), 5 in the first (13 against 13), and 4 in the first, ending at 17 against 13. Difference 4. But 8 and 7 against 6, 5 and 4 is 15 against 15, difference 0. Greedy is wrong by 4 on five numbers.
That is what makes greedy dangerous here. It passes most small inputs you would invent by hand, so the bug survives your own testing. Both of those inputs are declared tests below.
A subset-sum table over the totals cannot be built either. The numbers reach 10^9, so the totals reach 4 * 10^10, and that is far past any array length.
## Turn the split into one number
If one group has total p, the other necessarily has total minus p, because every number lands in exactly one group. So the difference is the absolute value of total minus twice p.
That is the move that makes the problem tractable. You are no longer searching over splits, which are structured objects, but over the single number p, and you want p as close to half the total as possible. Every reachable p corresponds to at least one split, and every split gives a reachable p, so nothing is gained or lost by the change of variable.
## Halve the list
Enumerate the reachable totals of the left half and of the right half, about 2^20 each. A reachable p is one left total plus one right total. Sort the left totals once.
For a fixed right total r, the best partner is the left total nearest to half the total minus r. In a sorted array, nearest is found by binary searching for the insertion point and then checking the entry on each side of it, because the nearest value may be just below or just above and there is no way to know which in advance.
## The boundary that breaks a careless implementation
Half of an odd total is not an integer. If you use integer division you land on the floor, and the true best partner can be the entry above it rather than the one below. Checking only the lower side gives a wrong answer whenever the total is odd and the optimum sits above the floor. Checking BOTH neighbours is what makes integer division safe here, and the five-ones case is the smallest input where it matters.
The second trap is seeding the answer. The worst possible difference is the whole total, which happens when one group is empty, so that is the correct starting value. Starting from zero returns zero on every input.
## Overflow
Totals reach 4 * 10^10, past the 32-bit signed limit of 2147483647, so the total, the group totals, and the difference all need 64 bits. Twice p reaches 8 * 10^10, so the doubling must happen in 64 bits as well, and in JavaScript it must not be written as a shift, because a shift truncates to 32 bits.
## Cost
2^(n/2) per half, one sort, and two array probes per right total. A few million steps at n = 40.
## Worked example
``` numbers 3 1 4 2 total 10, half 5
left half 3 1 reachable totals 0 1 3 4 right half 4 2 reachable totals 0 2 4 6 left totals sorted 0 1 3 4
r = 0 want 5 neighbours 4 and none p = 4 difference |10 - 8| = 2 r = 2 want 3 neighbours 3 and 4 p = 5 difference |10 - 10| = 0 r = 4 want 1 neighbours 1 and 3 p = 5 difference 0 r = 6 want -1 neighbours none and 0 p = 6 difference 2
answer 0 ```
### Constraints - 1 <= n <= 40 - 0 <= each number <= 10^9 - Totals reach 4 * 10^10, which does not fit in a 32-bit signed integer. Use a 64-bit type.