bidirectional - Algorithm to find subset within two sets of integers whose sums match

Question

I'm looking for an algorithm which can take two sets of integers (both positive and negative) and find subsets within each that have the same sum.

The problem is similar to the subset sum problem except that I'm looking for subsets on both sides.

Here's an example:

List A {4, 5, 9, 10, 1}

List B {21, 7, -4, 180}

So the only match here is: {10, 1, 4, 9} <=> {21, 7, -4}

Does anyone know if there are existing algorithms for this kinda problems?

So far, the only solution I have is a brute force approach which tries every combination but it performs in Exponential time and I've had to put a hard limit on the number of elements to consider to avoid it from taking too long.

The only other solution I can think of is to run a factorial on both lists and look for equalities there but that is still not very efficient and takes exponentially longer as the lists get bigger.

Answer 1

Like the subset sum problem, this problem is weakly NP-complete, so it has a solution that runs in time polynomial(M), where M is the sum of all numbers appearing in the problem instance. You can achieve that with dynamic programming. For each set you can generate all possible sums by filling a 2-dimensional binary table, where "true" at (k,m) means that a subset sum m can be achieved by picking some elements from the first k elements of the set.

You fill it iteratively - you set (k,m) to "true" if (k-1,m) is set to "true" (obviously, if you can get m from k-1 elements, you can get it from k elements by not picking the k-th) or if (k-1,m-d) is set to "true" where d is the value of k-th element in the set (the case where you pick the k-th element).

Filling the table gets you all the possible sums in the last column (the one representing the whole set). Do this for both sets and find common sums. You can backtrack the actual subsets representing the solutions by reversing the process which you used to fill the tables.