How to make combination, if any one of the element exists that can be added to make sum?

Question

To find all possible combinations that can be added to make given sum. Combinations can be formed with multiple elements and also if any single element exists.

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}

More Scenarios:

Input = [4,6,8,5,3]
target = 3
Output {4:3}

Input = [4,6,8,3,5,3]
target = 3
Output {5:3,3:3}

Input = [1,2,3,15]
target = 15
Output {3:15}

Below code covers for all above scenarios.

Scenarios to be handled, along with above.

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}

Input=[9,6,8,1,7] 
target=5 
Output={3:1,3:1,3:1,3:1,3:1}

As suggested by @Chris Doyle in previous question, will be using that code. (How to find indices and combinations that adds upto given sum?)

Code:

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))

Andrea Pollini · Accepted Answer · 2020-06-13 15:27:48Z

0

You can use dictionary comprehension

from itertools import combinations
l1 = [9,1, 2, 7, 6, 1, 5] 
target = 8

for i in range(len(l1)):
  for c in combinations(l1,i):
      if sum(c) == target:
        res = { i:x for i,x in enumerate(c)}
        print(res)

edited Jun 13, 2020 at 15:27

answered Jun 13, 2020 at 15:17

Andrea Pollini

2904 silver badges8 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to make combination, if any one of the element exists that can be added to make sum?

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related