如果存在可以添加总和的任何元素，如何进行组合? [英] How to make combination, if any one of the element exists that can be added to make sum?

问题描述

查找可以加和以得出给定总和的所有可能组合. 可以与multiple elements以及if any single element exists.

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.

输入:

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

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

输出:

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}

更多方案:

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}

下面的代码涵盖了以上所有情况.

要处理的方案以及以上内容.

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}

如上一个问题中的@Chris Doyle所建议，

将使用该代码. (如何查找加起来等于给定总和?)

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

代码:

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

推荐答案

您可以使用字典理解

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)

这篇关于如果存在可以添加总和的任何元素，如何进行组合?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！