Partition Equal Subset Sum

Problem

Given a list of positive integers nums, decide whether it can be split into two groups whose sums are equal. Every element must go into exactly one group. Return True if such a split exists and False otherwise.

• nums holds up to a couple hundred positive integers.
• Each value is at most a few hundred.

Examples

• nums = [3, 8, 4, 7] → True. {3, 8} and {4, 7} both sum to 11.
• nums = [2, 4, 9, 6] → False. The total is 21, which is odd, so no equal split exists.
• nums = [2, 3, 4, 7] → False. Total 16, but no subset sums to 8.

Hints

1. If the two groups have equal sums, what does that say about the total, and what single number must one group add up to?
2. The question becomes "is there a subset with sum S". For each element, you either put it in that subset or you do not.
3. 0/1 knapsack over reachable sums: a boolean table can[s] updated for each element with s iterated downwards.