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:
- We sort the array.
- Initialize another variable temp to $0$.
- We traverse from highest element to lowest element.
- 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?