# Iterative 8-line solution using C(n, k) = C(n-1, k) + C(n-1, k-1)

• Raw solution:

``````def combine(self, NN, K):
result = [[[]]]
for n in range(1, NN+1):
newRes = [[[]]]  #C(n, 0) = 0
for k in range(1, n):
#C(n, k) = C(n-1, k) + C(n-1, k-1)
newRes.append(result[k] + [_ + [n] for _ in result[k-1]])
#C(n, n) = C(n-1, n-1) = 1
newRes.append([result[n-1][0] + [n]])
result = newRes
return result[K]
``````

After speed up:

``````def combine(self, NN, K):
result = [[[]]]
for n in range(1, NN+1):
newRes = [[[]]]  #C(n, 0) = 0
#speed up, ignore C(n, K+1),  C(n, K+2), C(n, K+3)...
for k in range(1, min(K+1, n)):
#C(n, k) = C(n-1, k) + C(n-1, k-1)
newRes.append(result[k] + [_ + [n] for _ in result[k-1]])
if n < K + 1:
newRes.append([result[n-1][0] + [n]]) #C(n, n) = C(n-1, n-1) = 1
result = newRes
return result[K]
``````

After space compression:

``````def combine(self, NN, K):
result = [[[]]]
for n in range(1, NN+1):
lastRes = result[0]
for k in range(1, n):
#C(n, k) = C(n-1, k) + C(n-1, k-1)
lastRes, result[k] = result[k], result[k] + [_ + [n] for _ in lastRes]
#C(n, n) = C(n-1, n-1) = 1
result.append([lastRes[0] + [n]])
return result[K]``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.