From where did that 117 come?

It suffices to show that there exist two non-empty subsets of $M$ having the same sum, as we can delete the common elements from both sets. Now, barring the empty set and the whole set $M$ , there are $2^{10}-2=1022$ different subsets of $M$ . Also, the minimum sum of the elements of any non-empty subset of $M$ is $1$ and the maximum sum of elements of any subset (not equal to $M$ ) is at most $109+ \ldots + 117=1017 .$ Hence, by the pigeonhole principle, there exist two non-empty subsets of $M$ having the same sum.

This is a sweet application of pigeon hole problem. A same type of problem appeared in one of those early days PUTNAM, which I solved earlier. So, first let's calculate the highest possible sum, and that is the sum of largest 9 numbers, I.e. 117,116,115,114,113,112,111,110,109. And the grand sum is 1017. And the least possible sum is 1 . And possible number of subsets is $2^{10}$ -2 I.e. 1022. So, here the number of pigeons is 1022 and no of holes is I.e. the number of various sums is 1016. And thus ….. BINGO!