Python standard backtracking beats 90%


  • 0
    W
    def combinationSum3(self, k, n):
        ret = []
        self.dfs(k, n, 0, [], ret)
        return ret
    
    def dfs(self, k, n, index, cur, ret):
        if index >= k:
            if sum(cur) == n:
                ret.append(cur)
            return
        start = 1 if not cur else cur[-1] + 1
        for i in range(start, 10):
            if sum(cur) <= n:
                self.dfs(k, n, index+1, cur + [i], ret)

Log in to reply
 

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