# Two ways in python, recursive and DP

• the recursive way is really simple:

``````def combine(self, n, k):

if k==1:
return [[i+1] for i in range(n)]

return [r+[n] for r in self.combine(n-1, k-1)]+self.combine(n-1,k) if n-1>=k else [r+[n] for r in self.combine(n-1, k-1)]
``````

You can certainly combine this thing into one line, but there is no point doing so.

The DP way:

``````def combine(self, n, k):
base=[[[j] for j in xrange(1, i+1)] for i in xrange(1, n+1)]
for height in xrange(k-1):
newBase=[[]]
for i in xrange(1, len(base)):
newBase.append(newBase[-1]+[b+[height+i+1] for b in  base[i-1]])
base=newBase[1:]
return base[-1]
``````

The var height means k values 1 to k, I did not find a better name.

DP runs ~60ms, recursive ~68ms, decent for python.

• ``````class Solution(object):

def combine(self, n, k):
dp = [[None]*(k+1)]*(n+1)
return self.helper(n,k,dp)

def helper(self,n,k,dp):
if dp[n][k] != None:
return dp[n][k]
if k==1:
dp[n][k] = [[i+1] for i in range(n)]
return dp[n][k]
if n-1>=k:
dp[n][k] = [r+[n] for r in self.helper(n-1,k-1,dp)] + self.helper(n-1,k,dp)
else:
dp[n][k] = [range(1,n+1)]
return dp[n][k]
``````

Can any one tell me why this is returning duplicates... I actually derived it from recursive version of this post...

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