I have two sorted lists of numbers in Python whose summation of their elements is equal. I suppose to analyze these two lists together. Simply put, I want to find some elements from the first list which equals one element from the 2nd list. If there are multiple combinations, I need to find all the combinations.
For example:
List1=[29,32,51,76,80,89] #==> 29+32+51+76+80+89=357
List2=[156,201] #==> 156+201=357
Result:
[
[[29,51,76],156], # Combination 1
[[76,80],156], # Combination 2
[[29,32,51,89],201], # Combination 1
[[32,80,89],201] # Combination 2
]
I tried to find some way with the "For" loop but its performance was too low and depends on the number of elements.
I don't see a faster way than creating all possible subsets of l1, calculating the sum and checking if it exists in l2:
import itertools
l1 = [29, 32, 51, 76, 80, 89]
l2 = set([156, 201])
for r in range(1, len(l1) + 1):
for sublist in itertools.combinations(l1, r):
if sum(sublist) in l2:
print(sublist, sum(sublist))
this prints
(76, 80) 156
(29, 51, 76) 156
(32, 80, 89) 201
(29, 32, 51, 89) 201