How to prove that following algorithm is correct? Suppose I have some $n$ numbers which are powers of $2$, say $a_1,a_2,a_3.....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 lot of arguments and verification, but i am not able to prove it:

*

*Sort the array and star.

*Traverse from highest element to lowest element.

*Let initialize another variable $temp = 0$

*If $temp>num$ then subtract $a_i$ else add $a_i$ . If in end $temp=num$ then it's possible to assign signs such that we can make $num$ out the array else not possible.

See an example in comment section.
How can I prove it?
 A: So, you have a target value, $T$, that you want to reach by adding/subtracting some given numbers $a_1, \ldots, a_n$.  Each $a_i$ must appear in the sum,  but you are allowed to choose whether each $a_i$ is added or subtracted.  In other words, you want to choose signs $s_i\in \{ 1, -1\}$ so that
$$
\sum s_i a_i = T,
$$
or else determine that no such choice is possible.
If I understand correctly, your algorithm is: Start with the biggest $a_i$. (If there are no $a_i$, meaning that $n=0$, then there is nothing to do! So assume $n\geq 1$.)  If $T\geq 0$, then choose $s_i = 1$.  If $T< 0$, then choose $s_i = -1$.  (Note: if $T=0$ then it really doesn't matter what choice you make; if it works one way then it will work the other way by flipping all the remaining signs.)  Now update the target: the new target $T'$ is given by $T' = T - s_i a_i$.  Repeat until there are no more $a_i$ left.
There is another assumption which I haven't mentioned yet: you said that each $a_i$ is a power of $2$.  It's a good thing that we have that assumption: if we didn't, then this algorithm doesn't work.  Example: $a_1 = 6, a_2 = 6, a_3= 9$, and $T=3$.  The algorithm would say to choose $9$ to have a positive sign.  But now you need to make $-6$ out of the remaining $a_i$, and there is no way to add/subtract a pair of $6$'s and get a result of $-6$.  (Instead, you can do $3 = -9 + 6 + 6$,  a valid solution which the algorithm as stated would not find.)
OK, so we make the further assumption that every $a_i$ is a power of $2$: write $a_i = 2^{k_i}$ for each $i$.  We may as well assume that they are in order, so
$$
0 \leq k_1 \leq k_2 \ldots \leq k_n .
$$
We may assume WLOG that $T\geq 0$ (otherwise just flip all the signs).  This would mean that you your algorithm says to choose $s_n = 1$.
Now, to prove that your algorithm is optimal is kind of a tricky thing!  Optimality means that, IF it would work to make the OTHER choice, THEN it STILL works to make the choice you do.
OK, so: suppose that there is a valid choice of signs $(t_1, \ldots, t_n)$, with $t_n = -1$, such that $\sum t_i a_i = T$. We need to show that there is another valid choice $(s_1, \ldots, s_n)$ with $s_n = 1$.
That is, assume that
$$
t_1 a_1 + \ldots + t_{n-1} a_{n-1} = T + 2^{k_n},
$$
and show that there exist $s_1, \ldots , s_{n-1}$ such that
$$
s_1 a_1 + \ldots + s_{n-1} a_{n-1} = T - 2^{k_n}.
$$
Basically, we need to flip the signs on some of the $t_i$, and by doing so, decrease the sum by just the right amount.  This will certainly mean flipping some of the positive $t_i$ to negative.
Maybe we can get away with ONLY flipping from positive to negative!
So, for convenience let's restrict our attention to just the $a_i$ for which $t_i$ is positive; let these be $b_1, \ldots , b_m$.  Clearly there are some of these; indeed,
$$
b_1 + \ldots + b_m \geq T + 2^{k_n} > 0
$$
since counting only the positive terms (removing negative terms) can only increase the resulting sum.  (Thus $m\geq 1$.)  We still assume they are written in order; write $b_i = 2^{\alpha_i}$ where
$$
0 \leq \alpha_1 \leq \ldots \leq \alpha_m.
$$
Notice that subtracting these terms INSTEAD of adding them will reduce the sum by twice the sum of these terms.  We need to reduce the sum by $2\cdot 2^{k_n}$, so we need to show that there is a subset $C\subseteq \{ 1, \ldots, m\}$ such that
$$
\sum_{i\in C} b_i = 2^{ k_n}.
$$
Write $N=k_n$ for convenience.  Also, notice that $2^{\alpha_m} = b_m \leq a_{n-1} \leq a_n = 2^{N}$, so $\alpha_m \leq N$.
Now, if $b_m = 2^{N}$ then just flip that term and we're done.  So we can assume that $\alpha_m < N$.   That is, $\alpha_m \leq N  - 1$.
Here's the trick.  There must be some $i$ such that $b_i = b_{i+1}$.  For, if not, then
$$
b_1 + \ldots + b_m \leq 1 + 2 + 4 + \ldots + 2^{\alpha_m} \leq 2^N - 1 < 2^N,
$$
but we already said that $\sum b_i \geq 2^N + T \geq 2^N$.
So, there are two adjacent $b_i$ that share the same value.  Suppose that we REPLACE those two instances of $2^{\alpha_i}$ with a single instance of $2^{1 + \alpha_i}$.  The sum of the terms remains unchanged, and every term is still a power of $2$.
Now, continue combining duplicate terms until either there are no duplicates, or you make an instance of $2^N$.  Eventually you will make an instance of a $2^j$ for $j \geq N$, by the exact argument we already gave.  And the very first time you do so, the value of $j$ must be equal to $N$, because you have
$$
2^N \leq 2^j = 2^{j-1} + 2^{j-1}
$$
where $j-1 < N$.
So there is some collection of $b_i$ which sum to $2^N$. $\Box$
What we have shown is that choosing $s_n=1$ for $T\geq 0$ is not a mistake; it doesn't result in changing from "a solution exists" to "no solution exists".  (By contrast, in the $6,6,9$ example above, it was a mistake to add $9$.)  But if the algorithm never makes a mistake, then it is optimal.
