Match list elements from two lists that sum to the same amount

Question

I have two lists of numbers (A and B), and some combination of elements in A should sum to the same total as some combination of elements in B. As groups are matched, the matched elements would be removed from their lists to continue until all combinations are matched.

For example, with the two lists:

A = [7, 8, 12, 300, 350]
B = [3, 4, 20, 150, 500]

The combined sum totals of the matched groups would be:

{7: [{'A': [7], 'B': [3, 4]}],
 20: [{'A': [8, 12], 'B': [20]}],
 650: [{'A': [300, 350], 'B': [150, 500]}]}

The naive way I've addressed this so far is to get the sum of all possible combinations from each list (pow(2, len(mylist))-1), do a set intersection between the two sets of all combinations, and remove elements sequentially until all elements are accounted for.

Does anyone know of a more efficient algorithm to accomplish this? Expanding to all possible combinations for each list to then do a set intersection can get large.

Here's the naive way:

def getCombos(stuff):
    res = []
    for L in range(1, len(stuff) + 1):
        for subset in itertools.combinations(stuff, L):
            res.append(subset)
    return res

Acombo = getCombos(A)
Bcombo = getCombos(B)
AcomboSum = [sum(tup) for tup in Acombo]
BcomboSum = [sum(tup) for tup in Bcombo]

sumint = sorted(set(AcomboSum).intersection(set(BcomboSum)))

Arem = [a for a in A]
Brem = [b for b in B]

d = collections.defaultdict(list)

for s in sumint:
    idx = sumint.index(s)
    Avals = Acombo[AcomboSum.index(s)]
    Bvals = Bcombo[BcomboSum.index(s)]

    if set(Avals).issubset(set(Arem)) and set(Bvals).issubset(set(Brem)):
        d[s].append([Avals, Bvals])
        for v in Avals: Arem.pop(Arem.index(v))
        for v in Bvals: Brem.pop(Brem.index(v))
    else:
        continue

print(d)

Answer 1

Sort both arrays in reverse descending order.

Then calculate all sums in array A and Sort that in reverse descending order.

if A[n] represents all elements in array A

and B[m] represents all elements in array B

and sum_A[n!] represents all possible sums of elements in A.

and sum_A.sorted(reverse=True) represents that array sorted in descending order.

create a new array B_start[n!] and store the index i of the first element in B that is smaller than the sum_A[i].

Now for any sum_A[i] element you only have to consider elements in B from B[ B_start[i] ] to B[m] for combinations of sums

Note: this only works if all numbers in the arrays are positive.