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

10,941
4
38
59

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

score 0 · Answer 2 · edited Dec 22 '22 at 13:29

a = [50, 50, 50, 50, 75, 75]
b = 125
lst = []
def temp(a,b):
    for i in range(0,len(a)):
        for j in range(i+1,len(a)):
            if((a[i]+a[j]==b)&(len(lst)==0)):
                print(i,j)
                lst.append(i)
                lst.append(j)
temp(a,b)
print(lst)

The above code creates a populated array called a, and an empty one called lst, along with a variable called b.

The function temp, which takes two parameters of a and b loops through the list a and then loops through the list a again with a positive offset of one while checking if the current and the next number added together equal b.

If the two numbers added together equal b and the list lst is empty, the code prints the index of the two numbers, and adds the index of the two numbers to the list lst

Finally the list lst is printed.

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

2 Answers2