Finding number of integer partitions I am trying to find number of integer partitions of given n - number. If I have n == 4, the answer should be 5 because:


\$4 = 1+1+1+1\$
\$4 = 2+1+1\$
\$4 = 3+1\$
\$4 = 2+2\$
\$4 = 4\$


My code works properly but the matter is that it counts big numbers for a very long time. I have no idea how to optimize my code. Maybe you can help me to make it faster?

def get_answer(n):
    if n == 0:
        yield []
        return
    for p in get_answer(n-1):
        yield [1] + p
        if p and (len(p) &lt; 2 or p[1] &gt; p[0]):
            yield [p[0] + 1] + p[1:]
number_of_partitions=lambda n:sum(1 for _ in get_answer(n))
A slightly more efficient dynamic programming approach means you only need O(n) space:

def partitions(n):
    parts = [1]+[0]*n
    for t in range(1, n+1):
        for i, x in enumerate(range(t, n+1)):
            parts[x] += parts[i]
    return parts[n]

In []:
partitions(50)

Out[]:
204226


Note: this is trivial to extend to the coin change problem (the number of ways you can make change with certain coins: Ways to make change for a dollar), by restricted the values in the outer loop, e.g.:

def coin_change(n, coins):
    parts = [1]+[0]*n
    for c in coins:
        for i, x in enumerate(range(c, n+1)):
            parts[x] += parts[i]
    return parts[n]

In []:
coin_change(100, {1, 5, 10, 25, 50, 100})

Out[]:
293