查找给定整数集的所有组合，总和达到给定总和

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

这被称为“变革问题”，它\xe2\x80\x99是动态规划的一个经典示例的一个经典示例。

\n

一些早期的答案已经计算了解决方案的总数，而问题则要求进行枚举可能的解决方案。

\n

您尚未用语言标记您的问题，因此这里是 Python 中的实现。通过使用您语言的“bag”数据类型（Counter Python 的“bag”），使其适应您喜欢的任何语言。

\n

from collections import Counter\n\ndef ways(total, coins):\n    ways = [[Counter()]] + [[] for _ in range(total)]\n    for coin in coins:\n        for i in range(coin, total + 1):\n            ways[i] += [way + Counter({coin: 1}) for way in ways[i-coin]]\n    return ways[total]\n

\n

输出数据类型是包列表。

\n

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

\n