On: The Easiest Hard Problem (2002)

[vog]

You misunderstood the question. This is not about partitions. The union of the subsets is not required to be the full set. See also: https://news.ycombinator.com/item?id=10023034

And no, I don't think the proof would not work when requiring the two subsets to form a partition. Also note that for partitions, the number of sums would be one, as the only possible sum is half of the sum of all numbers. (And the problem would be unsolvable if the sum of all numbers was odd, but all numbers were still integers.)