Algorithm to find combination of signs of integers in a set such that the set sums to 0

Question

Given a set S of n positive integers, we want to know if we can find a combination of signs for each of the numbers in S (+ or -) such that the sum of S is 0.

How can one efficiently solve this problem? Based on similar problems, I'd imagine some kind of dynamic programming is in order. Is there any literature on this specific problem (I am having trouble finding it).

I guess this is similar to the subset sum problem. However, now we have to use the entire set, and for each integer s_i we can include -s_i or +s_i, but not both.

Answer 1

Given that the problem seem to be NP-complete, using a SAT, MILP, CP or ASP solver is the best choice, as these are tailored to solve these kind of problems.

Solution

Here is a solution using ASP (Answer Set Programming).

Given a file instance.lp:

value(12).
value(12).
value(1).
value(2).
value(3).
value(5).
value(6).
value(7).

and the file encoding.lp:

% every value can be positive (or not)
{pos(X)} :- value(X).

% fail if the sum is not 0
:- not 0 = #sum {V : pos(V); -V : not pos(V), value(V)}.

% format output
#show pos/1.
#show neg(V) : not pos(V), value(V).

the problem can be solved using clingo, an ASP solver of the potassco tool collection (easily installable via conda, pip, Ubuntu Package Manger etc...).

Calling:

clingo instance.lp encoding.lp

gives you the result:

Answer: 1
pos(1) pos(2) pos(3) pos(5) pos(7) neg(6) neg(12)

You can enumerate all possible solutions with:

clingo instance.lp encoding.lp 0

giving you

Answer: 1
pos(1) pos(2) pos(3) pos(5) pos(7) neg(6) neg(12)
Answer: 2
pos(2) pos(3) pos(6) pos(7) neg(5) neg(1) neg(12)
Answer: 3
pos(5) pos(6) pos(7) neg(3) neg(2) neg(1) neg(12)
Answer: 4
pos(12) pos(1) pos(2) pos(3) neg(7) neg(6) neg(5)
Answer: 5
pos(12) pos(6) neg(7) neg(5) neg(3) neg(2) neg(1)
Answer: 6
pos(12) pos(1) pos(5) neg(7) neg(6) neg(3) neg(2)

ASP

Using ASP to solve the problem has the advantage of:

• beeing easily maintainable (very short description of the problem, easy to read)
• very fast (based on SAT and CDNL)
• declarative (you only describe the problem, not how to solve it)
• easily extensible with other constraints
• also able to do all kinds of optimization (like optimizing for the biggest subset to form the sum)

Edit You can also copy and paste the content of both files to check out the results yourself online, using a js compilation of clingo here