# Does this problem related to subset sum have a name?

I'm looking for research into this problem -- computational complexity, solution algorithms, approximation algorithms, etc. If it has a canonical name, that would help me look into prior research.

Suppose there are two sets of integers S1 and S2 that are subsets of the positive integers.

The sum of all numbers in S1 equals the sum of all numbers in S2.

Find all subsets of S1 and subsets of S2 such that the the subsets sum up equivalently between the two. For example:

S1 = (1,2,3,4) S2 = (2, 2, 3, 3)

solutions:

(1+2 = 3, 3 = 3, 4 = 2+2)
(1+2+3 = 3+3, 4 = 2+2)
(1+2+3+4 = 2+2+3+3)
(1+3 = 2+2, 2+4 = 3+3)
(1+3+4 = 2+3+3, 2=2)
(2+3 = 2+3, 1+4 = 2+3)
etc.

You could also frame this in terms of making all numbers in S2 negative, collapsing them into one set, and finding all permutation subsets such that each subset adds up to 0.

If the numbers in S2 are expressed as negative numbers, the problem could also be expressed as a graph in which each node is an integer, and the goal is to find all possible disjoint sets such that the members of each set add up to 0.

• Instead of listing all such partition pairs explicitly, it could also be interesting to list just the finest ones (in your example, these are (1+2=3,3=3,4=2+2),(1+3=2+2,2+4=3+3),(1+4=2+3,2=2,3=3)). These still uniquely determine the set of solutions. Jun 28, 2015 at 23:38

I've never heard of this problem before, but it's clearly NP-hard.

There's a simple polynomial time reduction from subset-sum to this problem. All you have to do is take an instance of subset-sum such as: {x1, x2, x3, ... , x_n} ...and map it to this instance of the problem you describe: S1 = {x1, x2, x3, ..., x_n}; S2 = {0}.

(I initially misread your question and thought that you were talking about a decision problem; since that was not what you meant, I cannot say anything beyond whether or not it is NP-hard except that it is EXPTIME. It is likely not NP; see the comments below.)

Either way, I don't think you are going to find any good solution or approximation algorithms.

• The question asks for all such subsets, so I don't think it belongs to NP. Jun 28, 2015 at 19:17
• Yes, as Austin points out it's not even a decision problem. It could take exponential time just to enumerate all such subsets (for example, if $S_1 = S_2 = \{1, \ldots, n\}$). Jun 28, 2015 at 19:22
• Oops...didn't read carefully enough. I'll edit in a moment.
– user1338
Jun 28, 2015 at 21:22