def part(n, k):

    def memoize(f):
        cache = [[([None] * n) for j in range(k)] for i in range(n)]

def wrapper(n, k, pre):
    if cache[n - 1][k - 1][pre - 1] is None:
        cache[n - 1][k - 1][pre - 1] = f(n, k, pre)
return cache[n - 1][k - 1][pre - 1]
return wrapper

@memoize
def _part(n, k, pre):
    if n <= 0:
        return []
if k == 1:
    if n <= pre:
        return [(n,)]
return []
ret = []
for i in range(min(pre, n), 0, -1):
    ret += [((i,) + sub) for sub in _part(n - i, k - 1, i)]
return ret
return _part(n, k, n)
Python Integer Partitioning with given k partitions