Negative numbers in Subset-Sum

Problem Detail: 

If I have a set $A$ with positive and negative numbers, and a number to find C.

It is possible to reduce the problem to one with only positive numbers in set $A$?

I mean, it is possible to find a new set $A$ and a new number $C$, so $A$ were only positive numbers, but the same problem?

Asked By : Pedro

Answered By : Yuval Filmus

Hint: Let $A = \{ a_1,\ldots,a_n \}$. Choose a large number $M$ and consider the set $\{ M + a_1, \ldots, M + a_n, M, \ldots, M \}$ ($n$ times the number $M$) and the target $nM + C$. If you want an actual set, instead of taking $n$ times the number $M$, take $M,2M,4M,\ldots,2^{\lceil \log_2 n \rceil}M$ (we assume that $0 \notin A$; otherwise, remove $0$ from $A$).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24050