Can it be split into two equal halves

Given a list of positive numbers, say whether it can be split into two groups with the same total. Every number must go into exactly one group.

Worked example#

[1, 5, 11, 5] totals 22, so each group would need 11. And 11 on its own matches 1 + 5 + 5, so the answer is true.

[1, 2, 3, 5] totals 11, which is odd. No split of an odd total can be even, so the answer is false without looking any further.

Saying it plainly#

If the total is T, each half must be T / 2. So the question is:

Is there a subset that adds up to exactly T / 2?

That is the subset sum problem, and this is it wearing a disguise. Half the work in dynamic programming is this translation: getting from the words to the question the table will answer.

Two things follow at once. An odd total is impossible, so answer false immediately. And you only need to look for one group, because whatever is left over is the other.

The table#

Let reachable[s] mean "some subset of the numbers seen so far adds up to s". Start with reachable[0] = true, since the empty subset sums to zero, and everything else false.

For each number, any sum s becomes reachable if s - value was already reachable. At the end, look at reachable[T / 2].

The backwards loop, and why#

Walking the sums downwards for each number is not a style choice, and getting it wrong is the classic bug:

for value in nums:
    for s from half down to value:
        if reachable[s - value]: reachable[s] = true

Going upwards, reachable[s - value] might have been set by this same number earlier in the same pass, and you would be using the number twice. Downwards, s - value is always a smaller index that this pass has not touched yet, so it still describes the previous numbers only.

If your answer comes out true too often, this loop is the first place to look.

What it costs#

n times T / 2 steps and one array of T / 2 booleans. That is called pseudo-polynomial: it is fast when the totals are small and gets slow when they are large, because the cost follows the size of the numbers rather than how many there are.

Constraints#

• 1 <= n <= 200
• 1 <= nums[i] <= 100