如何查找列表的哪些值求和为指定值

Question

我正在编程背包加密算法。我是Python编程的新手。我有一个列表和一个确定的整数值。我想查找列表中的哪些元素将总计为我的整数值。我可以让它运行两个或更少的元素，但不能运行两个以上的元素。

假设：

privkey = [2,3,6,13,27,52]
cipher = 9

我当前的功能可以运行上述方案：

searchList = []
for i, number in enumerate(privkey[:-1]):  
    complementary = cipher - number
    if complementary in privkey[i+1:]:  
        searchList.append(number)
        searchList.append(complementary)
        print("Solution Found: {} and {}".format(number, complementary))
        break
else:  
    print("No solutions exist")
print(searchList)

此的预期输出将为[3,6]，并且确实有效。

但是，如果将密码更改为要求三个以上字符之和的条件：

cipher = 11

这将需要privkey [0] + privkey [1] + privkey [2]的总和。

如何创建覆盖这些基础的代码？

Answer 1

您可以使用此代码（对于python3）。

from itertools import combinations

privkey = [2,3,6,13,27,52]
cipher = 9
character = 2  # change it to get sum of dynamic no. of character

possible_combination = list(combinations(privkey, character))

li =[each for each in possible_combination if sum(each) == cipher]
print("List-> ", *li)

输出：

(3, 6)

Answer 2

需要递归地完成。这是我构建的功能，可能未优化：

def find_sum(my_list, left_list, target):
    if sum(my_list) == target:
        return my_list

    # Add this condition if all the numbers are positive (e.g once you are over the target, don't continue to try numbers
    if sum(my_list) > target:
        return

    if len(left_list) == 0:
        return
    for i in range(len(left_list)):
        current_number = left_list.pop(0)
        my_list.append(current_number)
        result = find_sum(my_list, left_list, target)
        if result:
            return result
        my_list.pop()
        left_list.append(current_number)
    return

privkey = [2,3,6,13,27,52]
cipher = 11
print(find_sum([], privkey, cipher))

输出：

[2, 3, 6]