Split Into Three Equal Parts
Print yes if the numbers can be divided into THREE groups of equal total, using
every number exactly once, and no otherwise.
1 2 3 4 5 6 -> yes {1,6} {2,5} {3,4}
7 7 7 7 -> no the total 28 is not divisible by 3
Problem #422 splits into TWO groups, and there one table dimension is enough: the second group is whatever the first leaves behind, so tracking one subset total determines everything.
Three groups break that. Knowing one group's total leaves the remaining numbers to be split two ways, which is still an open question, so the state must track TWO totals.
## The state
Let part = total / 3. If the total is not divisible by 3, answer no immediately.
reachable(a, b) = some assignment of the numbers processed so far puts total a in
group 1 and total b in group 2
Group 3 is implied: it holds everything else. That is why two dimensions suffice for three groups, and it is the same "one dimension is free" argument that made #422 one-dimensional.
Each number goes to group 1, group 2, or group 3:
from (a, b): (a + v, b) (a, b + v) (a, b)
Cap both coordinates at part, since exceeding it can never be undone, and answer
yes exactly when (part, part) is reachable at the end.
## Why the third branch is not optional
(a, b) unchanged means the number went into group 3. Omitting that branch forces every
number into group 1 or group 2, and the consequence is sharper than it looks.
If every number goes into one of the first two groups then a + b equals the whole
total. Reaching a = b = part would then need total = 2 * part, that is
total = 2 * total / 3, which forces total = 0.
So with all values positive, dropping the third branch makes the answer no on EVERY
input. It is not a subtle loss of some solutions; it loses all of them.
## Processing one number at a time
The three branches all read the state from BEFORE the current number, so compute into a fresh set or array and swap. Updating in place lets one number land in two groups at once.
This is the two-dimensional version of the downward loop in 0/1 knapsack, and here the copy is the clearer way to get it right.
## Boundaries
1 2 3 answers no: the total 6 is divisible by 3 and part = 2, but no group can be
made from {1,2,3} three ways. Divisibility is necessary and not sufficient, and a
solution that checks only the total gets this wrong.
2 2 2 2 answers no because 8 is not divisible by 3, and 4 1 1 1 1 1 1 answers
no for the same reason, its total being 10.
1 1 1 answers yes with one number per group, and 3 3 3 likewise.