2 ms·
Here is a hint. Look at http://en.wikipedia.org/wiki/Pascal%27s_triangle http://en.wikipedia.org/wiki/Pascal%27s_triangle and ask yourself why the 23nd row can
by btilly 16y ago
Here is a hint. Look at http://en.wikipedia.org/wiki/Pascal%27s_triangle http://en.wikipedia.org/wiki/Pascal%27s_triangle and ask yourself why the 23nd row can be calculated without explicitly enumerating all possible subsets.
I'm pretty sure that cperciva used a similar trick, but in each row you're potentially adding another element of the set, and not potentially adding 1.
This gives you a mapping telling you how many ways there are to get 0, 1, 2, 3, etc as the sum of some subset of the set. Just sum this over the set, and subtract the size of the set. (Every element in the set is the sum of itself, but you don't want to count those.) And there is your answer.