Concise Python solutions, 5 lines, 44 ms

  • 0

    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:
        for i in xrange(start, min(1+n//k, 10)):
            self.DFS(k-1, n-i, pre+[i], i+1)

Log in to reply

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