Two Equal Piles as Tall as Possible
You are given n numbers. Build two piles out of some of them, leaving the rest unused, so that the two piles have the same total. Make that common total as large as you can, and print it.
Every number is either in the first pile, in the second pile, or unused. Leaving everything unused gives two empty piles of total 0, so 0 is always achievable and the answer is never negative.
## What most people try first
Try every assignment. There are 3^n of them, since each number has three destinations, and at n = 24 that is about 2.8 * 10^11. Too slow.
The standard trick for this shape is a table indexed by the DIFFERENCE between the two piles, carrying the best height reached at that difference. That is genuinely the right idea, and it is also why this problem is here rather than in the dynamic programming topic: the difference can be as large as the total, which reaches 2.4 * 10^10, so the table cannot be allocated. The idea survives; the array does not.
## Why this is not the subset version
Every earlier problem in this topic splits a two-way choice: an item is taken or it is not. A half of n items therefore has 2^(n/2) outcomes and each one is summarised by a single number, its total, so the join is a lookup or a search on one key.
Here each item goes to one of THREE places. A half has 3^(n/2) outcomes, and one number no longer summarises an outcome, because knowing the total that went to the first group tells you nothing about how the rest was divided between the second and third. So the join key has to carry more than a sum, and working out what the key must be is the whole problem.
The arithmetic still works in your favour, which is the point. 3^24 is about 2.8 * 10^11 and 3^12 is 531441.
## What the key must be
Track two things per assignment: the difference between the two piles, and the height of the first pile.
The difference is what has to cancel. If the left half ends at difference d then the right half must end at difference minus d, because the differences add. And among all left assignments that reach a given difference, only the one with the GREATEST first-pile height can ever be part of the best answer, because a taller first pile at the same difference means a taller second pile too.
So enumerate the left half into (difference, height) and keep, for each difference, only the maximum height. Then enumerate the right half, and for each right assignment of difference d and height h, look up the best left height at difference minus d and consider h plus that.
## Why keeping only the maximum per difference is safe
Two left assignments with the same difference are interchangeable as far as the rest of the problem is concerned: the right half only ever needs to know the difference in order to cancel it. Given the difference is fixed, the objective is increasing in the height, so the shorter of the two can never win. That is what makes the collapse from 3^(n/2) rows down to one row per distinct difference sound, and it is the same reasoning as a running maximum, applied to a key rather than to a sorted position.
## The boundary that breaks a careless implementation
Seeding the answer. Two empty piles are legal and give 0, so the answer starts at 0 and never goes negative. A solution seeded at minus infinity that never finds a match reports nonsense on the input where no non-empty balance exists.
The second is the unused option itself. It is easy to write the enumeration with only two branches and lose it, which turns the problem into the balanced-partition question and gives a smaller answer on almost every input.
## Overflow
Totals and differences reach 2.4 * 10^10, past the 32-bit signed limit of 2147483647, so every total, the difference, and the height need 64 bits. The difference can be negative, so the type must be signed.
## Cost
3^(n/2) to enumerate each half, which is 531441 at n = 24, plus a lookup per right assignment.
## Worked example
``` numbers 1 2 3 4 5
left half 1 2 (difference, height of the first pile) unused,unused (0,0) A,unused (1,1) B,unused (-1,0) unused,A (2,2) A,A (3,3) B,A (1,2) unused,B (-2,0) A,B (-1,1) B,B (-3,0) best height per difference -3:0 -2:0 -1:1 0:0 1:2 2:2 3:3
right half 3 4 5 one line of it, the assignment A=3+4, B=5, difference 2, height 7 needs a left difference of -2, whose best height is 0, giving 7
answer 7 (piles 3+4 and 5, with 1 and 2 unused) ```
### Constraints - 1 <= n <= 24 - 0 <= each number <= 10^9 - Totals and differences reach 2.4 * 10^10, past the 32-bit signed limit, and the difference can be negative, so a signed 64-bit type is required.