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?
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.