1

How to find the combinations and corresponding indices that adds upto given sum ? And also, can it be handled list of elements of size 500000 (higher size) ?

Input:

l1 = [9,1, 2, 7, 6, 1, 5] 
target = 8

**Constraints**
1<=(len(l1))<=500000
1<=each_list_element<=1000

Output:

Format : {index:element}
{1:1, 5:1, 4:6}   #Indices : 1,5,4   Elements : 1,1,6
{1:1, 2:2,  6:5}
{5:1, 2:2,  6:5}
{1:1,  3:7}
{5:1,  3:7}
{2:2,  4:6}

Tried:

from itertools import combinations

def test(l1, target):
    l2 = []
    l3 = []    
    if len(l1) > 0:
        for r in range(0,len(l1)+1):        
            l2 += list(combinations(l1, r))

        for i in l2:        
            if sum(i) == target:
                l3.append(i)

    return l3

l1 = [9,1, 2, 7, 6, 1, 5] 
target = 8
print(test(l1,target))

[(1, 7), (2, 6), (7, 1), (1, 2, 5), (1, 6, 1), (2, 1, 5)]

Can someone guide me ?

UPDATE

Apart from above, code fails to handle these scenarios
Input = [4,6,8,5,3]
target = 3

Outputs {} , need to output {4:3}

Input = [4,6,8,3,5,3]
target = 3

Outputs {} , need to output {5:3,3:3}   #corrected index

Input = [1,2,3,15]
target = 15

Outputs = {}, need to output {3:15}
Improve this question
5
  • Where is your code showing your effort to solve the issue or any issue in your code which doesnt work. I would suggest looking at things like itertools module for functions like combinations Commented Jun 12, 2020 at 16:16
  • @ChrisDoyle: Posted the solution above, which i tried. I couldn't keep track of corresponding indices here. Any better approach ? Keeping performance, execution time and handling larger number of elements in list. Commented Jun 12, 2020 at 16:45
  • @Chris Doyle : Any idea ? Commented Jun 12, 2020 at 18:04
  • Will the numbers in l1 always be unique? you can reduce the number of combinations by ignoring all numbers which are greater than the target. i would use enumerate to generate index, value tuples and then make combinations from those. Commented Jun 12, 2020 at 20:52
  • @Chris Doyle: may be unique sometimes but duplication of elements also exist. In that case, we need to consider them. Input =[1,6,7,1,3], target=5, Output={0:1,3:1,4:3} , {0:1,0:1,4:3}, {3:1,3:1,4:3}. Should I create separate question for this ? Commented Jun 13, 2020 at 13:19

2 Answers 2

Reset to default
2

Your code was close, i would use enumerate to get the index and value as tuple pairs. I am always dropping any of the index and value tuples where that value is greater than the target since that cannot possible be a match. this will generate less combinations. Then like you i just iterate through the permutations of tuples and sum the values in each permutation, if it sums to the target then yield that permutation. lastly in the loop to output the values i give the perm to dict to convert into the dict format you wanted

from itertools import combinations


def find_sum_with_index(l1, target):
    index_vals = [iv for iv in enumerate(l1) if iv[1] < target]
    for r in range(1, len(index_vals) + 1):
        for perm in combinations(index_vals, r):
            if sum([p[1] for p in perm]) == target:
                yield perm


l1 = [9, 1, 2, 7, 6, 1, 5]
target = 8
for match in find_sum_with_index(l1, target):
    print(dict(match))

OUTPUT

{1: 1, 3: 7}
{2: 2, 4: 6}
{3: 7, 5: 1}
{1: 1, 2: 2, 6: 5}
{1: 1, 4: 6, 5: 1}
{2: 2, 5: 1, 6: 5}
Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

Interesting. Looks good but fails to handle few scenarios, updated question with scenarios in UPDATE section.
you really couldnt tell what in my code you needed to update to make it work for your new examples?
just change if iv[1] < target to if iv[1] <= target as i was only keeping numbers that were less than the target as i has assumed you only wanted to finds nums that summed to the target, i didnt consider a single instance combination to match the target
Excellent, that's right. Apologize, I didn't notice that. Thanks Chris.
Was thinking of another scenario. If input=[9,6,8,1,7] and target=5 and output={3:1,3:1,3:1,3:1,3:1,3:1}. Since, 1 can be added 5 times to make it to target.
|
0

You can just use index function to get index and store them as key:value pair with help of dictionary in another list such as following,

from itertools import combinations

def test(l1, target):
    l2 = []
    l3 = []
    l4=[]
    dict1={}
    a=0
    if len(l1) > 0:
        for r in range(0,len(l1)+1):        
            l2 += list(combinations(l1, r))

        for i in l2:
            dict1={}
            if sum(i) == target:

                for j in i:
                    a=l1.index(j)
                    dict1[a]=j
                l4.append(dict1)
                l3.append(i)

    return l4

l1 = [4,6,8,5,3]
target = 3

print(test(l1,target))

output:

[{4: 3}]

as you can see the condition l1 = [4,6,8,5,3] target = 3 works which is previously not working.

Hope this helps!

Improve this answer

2 Comments

Input = [4,6,8,3,5,3] , target=3, it prints [{3: 3}, {3: 3}] instead of {5:3,3:3}. And moreover, it should be of a single dictionary, consisting these combinations.
that's the problem with having multiple same values,because i have used index() method it returns the index of first appearance of that value.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.