找到所有可能的子集，使它们的总和等于给定的数字

Question

我正在学习Python，遇到了一个看似简单的问题。

我想要找到所有可能的数字组合，使它们相加等于给定的数字。
例如：4 -> [1,1,1,1] [1,1,2] [2,2] [1,3]

我的解决方案是生成所有可能的子集（2^n），然后筛选出那些和为给定数字的子集。但我在条件上遇到了问题。代码如下：

def allSum(number):
    #mask = [0] * number
    for i in xrange(2**number):
        subSet = []
        for j in xrange(number):
            #if :
                subSet.append(j)
        if sum(subSet) == number:
           yield subSet



for i in allSum(4):
    print i   

顺便问一下，这是一个好方法吗？

- Lukasz Madon

---

这些被称为分区。 - interjay

所以我猜 3,1,0, 和 3,1,0,0 以及 3,1,0,0,0,0,0,0,0... 都不行了？ :) - corsiKa

ye :P 空子集和元素 j 应满足 0 < j <= n。 - Lukasz Madon

@lukas 在我为你的问题实现了一个完美的解决方案时，问题被关闭了。我认为它非常高效。无论如何，请在这里查看：http://ideone.com/ZFQYL - zerm

@zerm 我重新打开了这个问题，因为它与被标记为重复的问题有很大不同。请随意将您的解决方案作为答案发布。 - NullUserException

Answer 1

以下是我几年前看到并能够解决问题的代码：

>>> def partitions(n):
        if n:
            for subpart in partitions(n-1):
                yield [1] + subpart
                if subpart and (len(subpart) < 2 or subpart[1] > subpart[0]):
                    yield [subpart[0] + 1] + subpart[1:]
        else:
            yield []

>>> print list(partitions(4))
[[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]]

附加参考资料：

• http://mathworld.wolfram.com/Partition.html（英文）
• http://en.wikipedia.org/wiki/Partition_(number_theory)（英文）
• http://www.site.uottawa.ca/~ivan/F49-int-part.pdf（英文）

这些是关于整数划分的额外参考资料，供您参考。

- Raymond Hettinger

Answer 2

那个解决方案不起作用，对吧？它永远不会将数字添加到子集中超过一次，因此您永远不会得到例如[1,1,2]。它也永远不会跳过一个数字，因此您永远不会得到例如[1,3]。

因此，您的解决方案存在两个问题：一，您实际上没有在范围1..number内生成所有可能的子集。二，所有子集的集合将排除应该包括的内容，因为它不允许数字出现超过一次。

这种问题可以概括为搜索问题。想象一下，您要尝试的数字是树上的节点，然后您可以使用深度优先搜索来查找表示解决方案的树中的所有路径。它是一个无限大的树，但幸运的是，您永远不需要搜索全部。

- user1064663

Answer 3

这里提供一种替代方法，它通过取一个由所有1组成的列表，并通过递归折叠来添加后续元素，这比生成所有可能的子集更有效率。

def allSum(number):
    def _collapse(lst):
        yield lst
        while len(lst) > 1:
            lst = lst[:-2] + [lst[-2] + lst[-1]]
            for prefix in _collapse(lst[:-1]):
                if not prefix or prefix[-1] <= lst[-1]:
                    yield prefix + [lst[-1]]
    return list(_collapse([1] * number))

>>> allSum(4)
[[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]]
>>> allSum(5)
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [1, 1, 3], [2, 3], [1, 4], [5]]

如果您不想要微不足道的情况，可以去掉最后一个值。如果您只需要循环遍历结果，请删除list调用并仅返回生成器。

- Andrew Clark

Answer 4

这相当于这个问题中描述的问题，可以使用类似的解决方案。

具体说明：

def allSum(number):
    for solution in possibilites(range(1, number+1), number):
        expanded = []
        for value, qty in zip(range(1, number+1), solution):
            expanded.extend([value]*qty)
        yield expanded

将这个问题翻译成那个问题，然后再反过来翻译回来。

- retracile