Generating the partitions of a number

I needed an algorithm to generate all possible partitions of a positive number, and I came up with one (posted as an answer), but it's exponential time.

The algorithm should return all the possible ways a number can be expressed as the sum of positive numbers less than or equal to itself. So for example for the number 5, the result would be:

• 5
• 4+1
• 3+2
• 3+1+1
• 2+2+1
• 2+1+1+1
• 1+1+1+1+1

So my question is: is there a more efficient algorithm for this?

EDIT: Question was titled "Sum decomposition of a number", since I didn't really know what this was called. ShreevatsaR pointed out that they were called "partitions," so I edited the question title accordingly.

Solution 1:

It's called Partitions. [Also see Wikipedia: Partition (number theory).]

The number of partitions p(n) grows exponentially, so anything you do to generate all partitions will necessarily have to take exponential time.

That said, you can do better than what your code does. See this, or its updated version in Python Algorithms and Data Structures by David Eppstein.

Solution 2:

Here's my solution (exponential time) in Python:

q = { 1: [[1]] }

def decompose(n):
    try:
        return q[n]
    except:
        pass

    result = [[n]]

    for i in range(1, n):
        a = n-i
        R = decompose(i)
        for r in R:
            if r[0] <= a:
                result.append([a] + r)

    q[n] = result
    return result

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