发现总结于给定号码的所有可能子集 [英] Find all possible subsets that sum up to a given number

问题描述

我正在学习Python和我有一个问题，这个看似简单的任务。

I'm learning Python and I have a problem with this seems to be simple task.

欲查找相加为一个给定数目的数字的所有可能的组合。
例如：4 - > [1,1,1,1] [1,1,2] [2,2] [1,3]

I want to find all possible combination of numbers that sum up to a given number.
for example: 4 -> [1,1,1,1] [1,1,2] [2,2] [1,3]

我挑选哪些生成所有可能子集（2 ^ n）和然后将溶液收率只是那些总和等于数。我的条件的问题。 code：

I pick the solution which generate all possible subsets (2^n) and then yield just those that sum is equal to the number. I have a problem with the condition. Code:

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   

BTW是一个不错的方法？

BTW is it a good approach?

推荐答案

下面是一些code我看到了几年前做的伎俩：

Here's some code I saw a few years ago that does the trick:

>>> 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/~伊万/ F49-INT-part.pdf

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

这篇关于发现总结于给定号码的所有可能子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！