Find All Possible Subsets That Sum Up To A Given Number

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

Solution 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) < 2or 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

Solution 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
        whilelen(lst) > 1:
            lst = lst[:-2] + [lst[-2] + lst[-1]]
            for prefix in _collapse(lst[:-1]):
                ifnot 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.

Solution 3:

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

To elaborate:

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

That translates this question into that question and back again.

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