3
$\begingroup$

Suppose that we're given $n$ integers $c_1, c_2, \dots, c_n$. We want to know if there is any assignment of $+$ and $-$ signs such that

$$ \pm c_1 \pm c_2 \dots \pm c_n = 0. $$

Does anyone know of a polynomial-time way to do this? Since there are $n$ integers, there are $2^n$ assignments of signs to consider, which grows rather quickly.

I've tried to phrase this problem in such a way that I can make use of dynamic programming, but DP usually lends itself to optimization sorts of problems, and this problem does not fall into that category (at least as stated).

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ There are pseudo-polynomial time algorithm (using DP) on the wiki page, time complexity $O(nS)$, where $S=\sum{c_i}$. Check your constraint to see if it meets your requirement. $\endgroup$
    – Terence Hang
    Commented Sep 19, 2015 at 17:07

1 Answer 1

Reset to default
7
$\begingroup$

Hint: This is just the well-known NP-complete problem PARTITION.

Improve this answer
$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.