Get indices of elements in a list that satisfies certain sum value

Question

I tried to get the indices of elements in a list, which summed of the value equal to certain number.

a = [50, 50, 50, 50, 75, 75]
b = 125

in the example above, I am looking for indices of element in list a that summed values equal to b (=125). indices combination that I am looking for is [0, 4], corresponding to the first number 50 and the first number 75.

I found a way by first creating possible combinations of the element in list a using itertools.combinations and then filter all combination that summed value equal to 125. it leads to indices [0,4], [1,4], [2,4],... This is quite problematic for list a that has many elements.

is there any simple way in python?

thank you.

Looking at this in hindsight, this seems to be a derivative of the subset-sum problem, which is NP-complete. There is no efficient algorithm to find what you're looking for save iterating through all possible combinations. — rayryeng, Apr 16 '18 at 21:07
See also https://stackoverflow.com/questions/6012963/subset-sum-problem — fferri, Apr 16 '18 at 21:09

score 0 · Answer 1 · answered Apr 17 '18 at 08:31

0

Try this:

 li = []
 for i,j in enumerate(a):
      for z,x in enumerate(a):
         if int(x)+int(j) == int(b) and i>z:
             li.append([i,z])

answered Apr 17 '18 at 08:31

Mehrdad Pedramfar

9,989
4
33
55

That only handles pairs of indices. What about triples? Quadruples? It's not just limited to pairs. – rayryeng Apr 17 '18 at 12:57

Get indices of elements in a list that satisfies certain sum value

1 Answers1