An integer partition of n is a weakly decreasing list of positive integers which sum to n.

For example, there are 7 integer partitions of 5:

[5], [4,1], [3,2], [3,1,1], [2,2,1], [2,1,1,1], [1,1,1,1,1].

Write a function named partitions which returns the number of integer partitions of n.  The function should be able to find the number of integer partitions of n for n as least as large as 100.

Difficulty: interview

Starter code:

def partitions(n):
	

Solutions:
def partitions(n):
    c = [[1]]
    for x in range(1, n + 1):
        c.append([0])
        for m in range(1, x + 1):
            c[x].append(c[x][m - 1] + c[x - m][min(m, x - m)])
    return c[n][n]

def partitions(n, k=1, cache={}):
    if k > n: return 0
    if n == k: return 1
    if (n,k) in cache: return cache[n,k]
    return cache.setdefault((n,k), partitions(n, k+1) + partitions(n-k, k))

ls = [1,1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627,792,1002,1255,1575,1958,2436,3010,3718,4565,5604,6842,8349,10143,12310,14883,17977,21637,26015,31185,37338,44583,53174,63261,75175,89134,105558,124754,147273,173525,204226,239943,281589,329931,386155,451276,526823,614154,715220,831820,966467,1121505,1300156,1505499,1741630,2012558,2323520,2679689,3087735,3554345,4087968,4697205,5392783,6185689,7089500,8118264,9289091,10619863,12132164,13848650,15796476,18004327,20506255,23338469,26543660,30167357,34262962,38887673,44108109,49995925,56634173,64112359,72533807,82010177,92669720,104651419,118114304,133230930,150198136,169229875,190569292]
def partitions(n):   
    return ls[n]

def partitions(n):
    part = [0] * (n + 1)
    part[0] = 1
    for i in range(1, n + 1):
        for j in range(i, n + 1):
            part[j] += part[j - i]
    return part[-1]

'''
            1                   n == 1 or m == 1
f(n,m) =     f(n,n-1)+1          m >= n
            f(n,m-1)+f(n-m,m)   m < n
'''
def partitions(n):
    d = {}
    for x in range(1, n+1):
        for y in range(1, n+1):
            if x == 1 or y == 1:
                d[(x,y)] = 1
            elif x <= y:
                d[(x,y)] = d[(x,x-1)] + 1
            else:
                d[(x,y)] = d[(x, y-1)] + d[(x-y,y)]
    return d[(n,n)]

from functools import lru_cache

@lru_cache(maxsize=None)
def partitions(n, start=1):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    return sum(partitions(n-i, i) for i in range(start, n+1))

dic={}
def partitions(n,x=None, maxx=None):
    x,maxx = (n,n) if x==None else (x,maxx)
    return sum([dic[(x-i,i)] if (x-i,i) in dic else(0 if dic.update({(x-i,i):partitions(n,x-i,i)}) else dic[(x-i,i)])for i in range(1,min([maxx,x])+1)[::-1]]) if x else 1

from functools import lru_cache

@lru_cache(maxsize=16384)
def partition_helper(sum, largest_number):
    if largest_number == 0: return 0
    if sum == 0: return 1
    if sum < 0: return 0
    return partition_helper(sum, largest_number - 1) + partition_helper(sum - largest_number, largest_number)

partitions = lambda n: partition_helper(n, n)

from functools import lru_cache


def partitions(n):
    return sum(part(n, k) for k in range(1, n+1))


@lru_cache(maxsize=None)
def part(n, k):
    return 1 if k in {1, n} else sum(part(n-k, i) for i in range(1, min(n-k, k)+1))

summ = list()


def partition(n, k):
    if n >= 0 and k >= 0 and summ[n][k] > 0:
        return summ[n][k]
    if n < 0:
        return 0
    if n <= 1 or k == 1:
        return 1
    summ[n][k] = partition(n, k - 1) + partition(n - k, k)
    return summ[n][k]


def partitions(n):
    n += 1
    for i in range(n):
        summ.append(list())
        for j in range(n):
            summ[i].append(-1)
    return partition(n - 1, n - 1)