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
