列表中数字的每个潜在组合

Question

我正在尝试使用列表中的元素生成给定数字的所有可能组合。例如，当数字为

4

并且列表包含

[1, 2]

时，有

3

可能的组合：

[1, 1, 1, 1] [2, 2] [1, 1, 2]

我向 ChatGPT 寻求帮助，以更好地理解这个概念，但提供的解释有些具有挑战性，特别是对于刚接触该主题的人来说。我的目标是在不依赖外部库的情况下为此任务创建代码。

Answer 1

您希望列表中的数字之和为给定数字。您可以通过迭代可能的数字组合并替换每个数字来暴力破解答案。最大组合尺寸将为

min(number_list) // target

。 IE。如果目标是

7

并且列表是

[2,3]

，则列表中最长的数字序列是

7 // 2

，即 3。

from itertools import combinations_with_replacement

def find_combinations(target, num_list):
    max_size = target // min(num_list)
    for r in range(1, max_size + 1):
        for combo in combinations_with_replacement(num_list, r):
            if sum(combo) == target:
                yield combo

在您的示例上运行代码：

for combo in find_combinations(4, [1,2]):
    print(combo)

# prints:
(2, 2)
(1, 1, 2)
(1, 1, 1, 1)

Answer 2

您可以使用动态规划来找到所有可能的解决方案，而不是暴力破解。为了避免一遍又一遍地进行相同的计算，缓存是必要的：

from functools import cache

@cache
def combs(number, nlist):
    if number == 0:
        return {tuple()}

    return {
        tuple(sorted([i, *c]))
        for i in nlist
        if i <= number
        for c in combs(number - i, nlist)
    }

但是，您需要对

tuple

参数使用

nlist

，因为

list

不能与缓存一起使用。