查找给定总和的给定整数集合的所有组合 [英] Find all combinations of a given set of integers summing up to a given sum

问题描述

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

I am looking for an answer to the following problem.

给出一组整数（无重复）和总和，找到该组元素的所有可能组合求和。解决方案顺序无关紧要（解决方案{2，2，3}和{3，2，2}相等）。

Given a set of integers (no duplicates) and a sum, find all possible combinations of the set's elements summing up to the sum. Solutions order does not matter (solutions {2, 2, 3} and {3, 2 ,2} are equal).

请注意，最终组合不需要

Please note that the final combination does not need to be a set, as it can contain duplicates.

示例：
设置{2,3,5}
总和10

Example: Set {2,3,5} Sum 10

结果：
{2，2，2，2，2}，{2，2，3，3}，{2，3，5}，{5， 5}

Result: {2, 2, 2, 2, 2}, {2, 2, 3, 3}, {2, 3, 5}, {5, 5}

我看过子集总和硬币找零问题，但无法适应他们的需求。我对动态编程不是很熟悉，所以它可能是可行的，但是我无法弄清楚。

I've looked at Subset Sum problem as well as Coin Change problem, but couldn't adapt them to suit my needs. I am not really familiar with dynamic programming, so it's probably doable, however I couldn't figure it out.

由于我要处理大量元素（大约50个），因此无法预计算所有集合，因为这将花费很长时间。 （如果可能）最好从子集和表中提取不同的解决方案。

As I am dealing with a fairly large set of elements (around 50), precomputing all the sets is not an option as it would take a very long time. A way to pull out different solutions from a Subset Sum table would be preferable (if possible).

任何建议，技巧或示例代码将不胜感激！

Any advice, tips, or sample code would be appreciated!

推荐答案

这称为变更问题，是动态编程。

一些较早的答案已计算出解决方案的总 count 个，而问题要求提供一个枚举可能的解决方案。

Some earlier answers have calculated the total count of solutions, whilst the question has asked for an enumeration of the possible solutions.

您尚未使用语言标记问题，因此这是Python的实现。通过使用您语言的袋数据类型将其调整为您喜欢的任何语言（n.b. Counter 是Python的袋）。

You haven't tagged your question with a language, so here's an implementation in Python. Adapt it to whatever language you please by using your language's "bag" datatype (n.b. the Counter is Python's "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]

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

The output datatype is a list of bags. Demo usage for printing them:

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

这篇关于查找给定总和的给定整数集合的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！