algorithm - 查找给定整数集的所有组合，总和为给定总和

Question

我正在寻找以下问题的答案。

给定一组整数(无重复项)和一个总和，求出该集合元素的所有可能组合，总和为总和。解决方案顺序无关紧要(解决方案 {2, 2, 3} 和 {3, 2 ,2} 相等)。

请注意，最终组合不需要是一个集合，因为它可以包含重复项。

例子: 设置 {2,3,5} 总结 10

结果: {2, 2, 2, 2, 2}, {2, 2, 3, 3}, {2, 3, 5}, {5, 5}

我看过子集和问题以及硬币找零问题，但无法调整它们以满足我的需要。我不太熟悉动态规划，所以它可能是可行的，但我想不通。

由于我要处理相当大的元素集(大约 50 个)，因此无法预先计算所有元素集，因为这会花费很长时间。从子集总和表中提取不同解决方案的方法会更好(如果可能)。

如有任何建议、提示或示例代码，我们将不胜感激!

Answer 1

这被称为 Change-making problem这是dynamic programming的经典例子.

一些较早的答案计算了解决方案的总数数量，而问题要求对可能的解决方案进行枚举。

您还没有用语言标记您的问题，所以这是 Python 中的一个实现。通过使用您语言的“bag”数据类型(Counter 是 Python 的“bag”)使其适应您喜欢的任何语言。

from collections import Counter

def ways(total, coins):
    ways = [[Counter()]] + [[] for _ in range(total)]
    for coin in coins:
        for i in range(coin, total + 1):
            ways[i] += [way + Counter({coin: 1}) for way in ways[i-coin]]
    return ways[total]

输出数据类型是包的列表。

>>> for way in ways(total=10, coins=(2,3,5)):
...     coins = (coin for coin,count in way.items() for _ in range(count))
...     print(*coins)
... 
2 2 2 2 2
2 2 3 3
2 3 5
5 5