On: The Easiest Hard Problem (2002)

[harryjo]

The number of partitions is 2^90 / 2, since each partition has 2 representations. (The rest of the proof still holds.)

[vog → harryjo]

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.)