求一组给定整数的所有组合，求和为给定和

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

解决方案复杂性：

• 时间：O（n*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];
}

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]]

半现场演示

Answer 3

这被称为变更问题，是动态编程中的一个经典例子。

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

您没有用语言标记您的问题，因此这里有一个Python实现。通过使用您的语言的“bag”数据类型（注意，计数器是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]

输出数据类型是包的列表。打印它们的演示用法：

>>> from __future__ import print_function  # for Python 2 compatibility
>>> 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