python dfs solution - TLE solved for the test case n=20, k=16


  • 1
    S
    class Solution(object):
        def combine(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: List[List[int]]
            """
            res = []
            if k==0 or n<1:
                return res
            
            self.dfs(n, k, [], res, 1)
            return res
            
        def dfs(self, n, k, path, res, index):
            length = len(path)
            #if len(path) == k:
            if length == k:
                res.append(path[:])
                return
            
            # TLE problem solved by adding this
            if k-length > n - index + 1: # need k numbers in total , still need (k-lenth)
                return
            
            for num in range(index, n+1):
                if num not in path:
                    path += [num]        
                    self.dfs(n, k, path, res, num+1)
                    path.pop()
    

Log in to reply
 

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