Concise Python solutions, 5 lines, 44 ms


  • 0
    C

    we only have to check the possible numbers. start is the starting (smallest) number. The maximum possible number is min(n//k,9) so we use the range xrange(start, min(1+n//k,10)).

    Solution 1, 5 lines

    def combinationSum3(self, k, n):
        def helper(k, n, start):
            if k==1:
                return [[n]] if start <= n < 10 else []
            return [ [i]+sub for i in xrange(start, min(1+n//k,10))
                             for sub in helper(k-1, n-i, i+1)] 
        return helper(k, n, 1)
    

    Solution 2, standard DFS

    def combinationSum3(self, k, n):
        self.ans = []
        self.DFS(k, n, [], 1)
        return self.ans
    
    def DFS(self, k, n, pre, start):
        if k==0:
            if n==0:
                self.ans.append(pre)
            return 
        for i in xrange(start, min(1+n//k, 10)):
            self.DFS(k-1, n-i, pre+[i], i+1)
        return

Log in to reply
 

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