Greedy algorithm for subset sum on powers of 2

Question

I have some $n$ numbers which are powers of $2$, say $a_1,a_2,a_3,\ldots,a_n$ which are not necessarily all distinct. I have option to give them any sign. I have to find if I can make their sum after that equal to num.

I have following algorithm which I am sure will work, by a lot of arguments and verification, but I am not able to prove it:

1. We sort the array.
2. Initialize another variable temp to $0$.
3. We traverse from highest element to lowest element.
4. If temp>num then subtract $a_i$, else add $a_i$. If in the end temp=num then it's possible to assign signs such that we can make num out the array, otherwise it is not possible.

How to prove that the algorithm works?

Answer 1

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 "1" in them and the rest are "0"s), now we can "flip" 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 < 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>0$, and notice this is the same as the first case.