Greedy algorithm for subset sum on powers of 2
You can prove the algorithm using induction. In order to prove by induction, your main statement would be: Let $s_n$ be the (correct) sign of $a_n$ (if it exists), then the algorithm trying to find $s^*_1,\dots,s^*_{n-1}$ such $\sum_{i=1}^{n-1} s^*_ia_i=num-s_na_n$ is correct (by induction assumption). Then, we only need to show that the algorithm chooses $s^*_n=s_n$ and then we would get $\sum_{i=1}^n s^*_ia_i=num-s_na_n+s^*_na_n=num$ as required.
Now the tricky part comes: how can we prove that the $s^*_n$ the algorithm chooses is indeed correct? We want to split this part into two cases:

$num\ge0$, and assume towards contradiction $s_n\neq 1$, i.e only $s_n=-1$ gives a valid solution (there may be multiple solutions, so beware of saying there is only one such $s_n$). Then we need to have $\sum_{i=1}^{n-1}s_ia_i = num+a_n$. Since we are dealing with only powers of $2$, and $a_n$ is the highest value, then there must be some values whose sum (when summed with the appropriate sign) is precisely $a_n$ (and this is because $a_n$ is also a power of 2, if you want a complete proof to this statement, think about the numbers as binary numbers with only one &quot;1&quot; in them and the rest are &quot;0&quot;s), now we can &quot;flip&quot; the sign of those values, and we would get $\sum_{i=1}^{n-1}=num-a_n$ (since their sum is $a_n$, the effect of flipping their sign is like subtructing $2a_n$) and then by choosing $s_n=+1$ we get $\sum_{i=1}^n s_ia_i=num$, in contradiction to our assumption.
$num &lt; 0$, we get that $s^*_n=-1$, and by flipping all of the signs as well as the sign of $num$ we get $s^*_n=1$ for $num&gt;0$, and notice this is the same as the first case.