# 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 '15 at 23:38

• 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 '15 at 19:22