从给定的值列表中查找固定长度的子列表的最快方法，其元素和等于定义的numb

Question

在Python3.6中，假设我有一个数字列表L，并且我想找到给定预先选择长度|S|的所有可能的子列表S，这样：

• 任何S的长度都必须小于L，即|S| < |L|
• 任何S只能包含L中的数字
• S中的数字不必是唯一的（它们可以重复出现）
• S中所有数字的总和应等于预先确定的数字N

使用笛卡尔积和itertools.product可以找到一个简单的解决方案。例如，假设L是1到10（包括1和10）之间所有整数的简单列表，|S|被选择为3。然后：

import itertools
L = range(1,11)
N = 8
Slength = 3
result = [list(seq) for seq in itertools.product(L, repeat=Slength) if sum(seq) == N]

然而，当选择较大的列表L和或较大的|S|时，上述方法变得非常缓慢。事实上，即使对L = range(1,101)和|S|=5和N=80来说，计算机几乎冻结，计算结果也需要大约一个小时。你知道吗

我的看法是：

• 考虑到子列表的总和应为N，在这种情况下，有许多不必要的计算正在进行
• 由于对itertools.product生成的数百万个列表进行迭代，从而只保留少得多的数据，因此会出现大量的缓存未命中

所以，我的问题/挑战是：有没有一种方法可以更有效地计算？除非我们讨论的是数百千兆字节，否则对我来说，速度比内存更为关键，因此，尽管考虑到内存效率是一个受欢迎的奖励，但挑战更多地集中在速度上。你知道吗

Answer 1

因此，给定一个输入列表和一个目标长度和总和，您需要输入列表中所有数字的排列：

1. 和等于目标和
2. 长度等于目标长度

以下代码应该更快：

# Input
input_list = range(1,101)

# Targets
target_sum = 15
target_length = 5

# Available numbers
numbers = set(input_list)

# Initialize the stack
stack = [[num] for num in numbers]

result = []

# Loop until we run out of permutations 
while stack:
    # Get a permutation from the stack
    current = stack.pop()

    # If it's too short
    if len(current) < target_length:
        # And the sum is too small
        if sum(current) < target_sum:
            # Then for each available number
            for num in numbers:
                # Append said number and put the resulting permutation back into the stack
                stack.append(current + [num])

    # If it's not too short and the sum equals the target, add to the result!
    elif sum(current) == target_sum:
        result.append(current)

print(len(result))