I seem to recall that there were 2^22 sets in the power set of that list of numbers, so you obviously had to use some kind of technique to cull the vast majority of the sets.
Hmm... now that I think about it, did you do something like starting at the end of the list, then subtracting numbers as you went until you either found a set that added up to your top number, or found it impossible for that number to be in the set?
It seems like it would take a lot of paper to do that, but it's more efficient than the simple brute force technique I did.
I'm just curious, because I bet there are better ways to do that one and I think the challenge is probably over by now.
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.
Hmm... now that I think about it, did you do something like starting at the end of the list, then subtracting numbers as you went until you either found a set that added up to your top number, or found it impossible for that number to be in the set?
It seems like it would take a lot of paper to do that, but it's more efficient than the simple brute force technique I did.
I'm just curious, because I bet there are better ways to do that one and I think the challenge is probably over by now.