Split Into Two Equal Halves
Print yes if the numbers can be divided into two groups with the SAME total,
and no otherwise. Every number must go into exactly one group.
1 5 11 5 -> yes (1 5 5) and (11)
1 2 3 5 -> no
The problem looks like an optimisation, "make the two groups as equal as possible", and it is not. It is a reachability question, and seeing that is the step that matters.
If the total is T, then two equal groups each total T/2. So:
T odd -> no, immediately
otherwise -> can some subset reach exactly T/2 ?
The odd check is not an optimisation, it is a correctness shortcut that also
prevents T/2 from being a non-integer.
What remains is problem #229, subset sum, with the target fixed. One boolean per reachable total:
reach[0] = true
for each value v:
for s from target down to v:
reach[s] = reach[s] or reach[s - v]
The DOWNWARD inner loop is the whole subtlety. Going upward lets one value be
used more than once, which answers a different question: whether the target is
reachable with repetition allowed. On [1, 2, 5] the upward version says yes,
since 1 + 1 + 2 = 4, and the true answer is no.