Two ways in python, recursive and DP


  • 0
    C

    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.


  • 0
    Y
    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...


Log in to reply
 

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