给定一个整数集合，找出所有相加等于给定总和的组合。

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个），预先计算所有集合不是一个选项，因为这将需要很长时间。如果可能的话，从子集和表中提取不同解决方案的方法将更可取。

任何建议、提示或示例代码都将不胜感激！

- Dzik

---

可能是Sum array values with sum equals X的重复问题。 - TiyebM

与子集和（允许集合或多重集）或无界背包问题并没有太大的区别。 - n. m.

你可以将此视为无限背包的特例，或子集和的泛化。无论哪种方式，枚举所有解决方案都需要完整的穷举搜索。可以使用DP找到一种解决方案。 - n. m.

如果你对DP不熟悉，现在是学习的好时机。很抱歉，我无法在SO评论甚至回答中解释它。 - n. m.

@wim 零钱找零问题通常旨在找到给出零钱的最佳方式（硬币数量最少），而不是每种可能的方式。 - n. m.

Answer 1

这被称为找零问题，是动态规划的一个经典例子。

一些早期的答案计算了解决方案的总数，而问题要求列举可能的解决方案。

您没有标记您的问题所用的语言，因此这里提供了Python的实现。通过使用您的语言的“包”数据类型（Counter是Python的“包”），可以将其适应到任何语言。

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

- wim

---

你如何处理重复项？例如，你可以想象你得到了2 2 3 3和2 3 3 2。 - zzzzzzz

Answer 2

这里是一个 Haskell 函数，用于计算答案：

partitions 0 xs = [[]]
partitions _ [] = []
partitions n (xxs@(x:xs)) | n < 0 = []
                          | otherwise = (map (x:) (partitions (n-x) xxs)) ++ partitions n xs

示例：

*Main>  partitions 1 [1]
[[1]]
*Main>  partitions 5 [1..5]
[[1,1,1,1,1],[1,1,1,2],[1,1,3],[1,2,2],[1,4],[2,3],[5]]
*Main> length $ partitions 10 [1..10]
42
*Main> length $ partitions 20 [1..20]
627
*Main> length $ partitions 40 [1..40]
37338
*Main> partitions 10 [1,2,4]
[[1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,2],[1,1,1,1,1,1,2,2],[1,1,1,1,1,1,4],[1,1,1,1,2,2,2],[1,1,1,1,2,4],[1,1,2,2,2,2],[1,1,2,2,4],[1,1,4,4],[2,2,2,2,2],[2,2,2,4],[2,4,4]]

半实时演示

- n. m.

Answer 3

解决方案复杂度：

• 时间：O(n*M)
• 空间：O(M)

其中M是总和的值，n是集合大小。

int numberOfSums(Set<Integer> values, int sum) {
    // sumCount[i] -> number of ways to get sum == i 
    int sumCount[] = new int[sum+1];
    sumCount[0] = 1;
    for(int v : values) {
        for(int i=0; i<=sum-v; ++i)
            sumCount[i+v] += sumCount[i];
    }
    return sumCount[sum];
}

- arvaladze