80+ms recursion python


  • 0
    L

    I think my code is easy to understand. I used 4 parameters in my recursive function, however only start and determined will be changed through the execution.

    class Solution:
        # @param {integer} n
        # @param {integer} k
        # @return {integer[][]}
        def __init__(self):
            self.ret = []
            
        def _combine(self, start, n, k, determined):
            if len(determined) == k:
                self.ret.append(determined)
                return
            for num in range(start, n+1):
                self._combine(num+1, n, k, determined+[num])
    
        def combine(self, n, k):
            if n < 1 or k > n:
                return
            self._combine(1, n, k, [])
            return self.ret

  • 0
    L

    I worked on reducing the parameters. Here is the improved solution with the same performance.

    class Solution:
        def combine(self, n, k):
            if k == 1:
                return [[x] for x in range(1, n+1)]
            ret = []
            for x in self.combine(n, k-1):
                for num in range(1, x[0]):
                    ret.append([num]+x)
            return ret

Log in to reply
 

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