Find all possible subsets that sum up to a given number

Question

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

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]

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 is it a good approach?

Answer 1

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

Additional References:

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

Answer 2

Here is an alternate approach which works by taking a list of all 1s and recursively collapsing it by adding subsequent elements, this should be more efficient than generating all possible subsets:

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

You can strip off the last value if you don't want the trivial case. If you will just be looping over the results remove the list call and just return the generator.

Answer 3

This is equivalent to the problem described in this question and can use a similar solution.

To elaborate:

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

That translates this question into that question and back again.

Answer 4

That solution doesn't work, right? It will never add a number to a subset more than once, so you will never get, for example, [1,1,2]. It will never skip a number, either, so you will never get, for example, [1,3].

So the problem with your solution is twofold: One, you are not actually generating all possible subsets in the range 1..number. Two, The set of all subsets will exclude things that you should be including, because it will not allow a number to appear more than once.

This kind of problem can be generalized as a search problem. Imagine that the numbers you want to try are nodes on a tree, and then you can use depth-first search to find all paths through the tree that represent a solution. It's an infinitely large tree, but luckily, you never need to search all of it.