# Finding suitable NP-complete problem to reduce to my problem

I've been given a set $S$ of natural numbers (non-negative integers) $s_1$, $s_2$,...,$s_n$ where $|S|=n$. My problem is to figure out if there is way to get a total sum of 0 when using all the numbers of $S$ but we get to "choose the sign" for each number: that is, for $s_i$ we get to choose if we're going to add or subtract $s_i$ from the total sum.

I've tried visualizing it using a directed cyclic graph with $n$ vertices where the only edges from $v_1$ to $v_2$ are $+/- s_1$ and the task is to traverse the whole graph, ultimately getting back to our starting node $v_1$ using a path with total weight 0.

What would be a suitable NP-complete problem to reduce into this one?

• Hint: PARTITION – Pontus Apr 20 '17 at 10:19
• Yes of course, that actually makes perfect sense.. I suppose you mean we can find a partitioning into two subsets with equal sum, and then for my application just negate one of them and the total result is zero? – Nyfiken Gul Apr 20 '17 at 10:27
• Exactly. As the differences between your problem and PARTITION are so superficial, one could even reasonably claim that they are the same problem. – Pontus Apr 20 '17 at 10:34
• You're absolutely right, it'll be a piece of cake from now on :) Thanks for your help Pontus! If you want to post it as an answer I'd gladly accept it. – Nyfiken Gul Apr 20 '17 at 10:46

This problem is essentially just a rephrasing of the classic NP-complete problem PARTITION. If you can partition a set $S$ of natural numbers into two partitions $S_1$ and $S_2$ with equal sum, then $\sum_{s \in S_1} s + \sum_{s \in S_2} -s = 0$ and vice versa.