Concise python solution using DFS


  • 9
    Y
    class Solution:
        # @param {integer} k
        # @param {integer} n
        # @return {integer[][]}
        def combinationSum3(self, k, n):
            if n > sum([i for i in range(1, 11)]):
                return []
    
            res = []
            self.sum_help(k, n, 1, [], res)
            return res
    
    
        def sum_help(self, k, n, curr, arr, res):
            if len(arr) == k:
                if sum(arr) == n:
                    res.append(list(arr))
                return
    
            if len(arr) > k or curr > 9:
                return
            
            for i in range(curr, 10):
                arr.append(i)
                self.sum_help(k, n, i + 1, arr, res)
                arr.pop()

  • 1

    Similar approach:

    class Solution(object):
        def combinationSum3(self, k, n):
            """
            :type k: int
            :type n: int
            :rtype: List[List[int]]
            """
            self.output = []
            arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
            self.compute([], arr, k, n)
            return self.output
        
        def compute(self, pre, post, k, n):
            if len(pre) == k and n == 0:
                self.output.append(pre)
            elif n < 0 or len(pre) > k:
                return
            else:
                for i in range(0, len(post)):
                    self.compute(pre+[post[i]], post[i+1:], k, n-post[i])
    

  • 1
    S

    Why you have to use list(arr) ? Isn't 'arr' already a list ?


  • 0
    A

    sum([i for i in range(1,11)]) ???
    shouldn't it be range(1,10)??


  • 0
    C

    I replace the line if n > sum([i for i in range(1, 11)]) with if n > sum([i for i in range(10-k, 10)]):
    It looks like better


  • 0
    C

    @swengzju You should make a copy of arr and add it to res rather than directly append arr to res. Otherwise any change in arr would change res too.


  • 0
    J

    few lines of code can be simplified.

    class Solution:
        # @param {integer} k
        # @param {integer} n
        # @return {integer[][]}
        def combinationSum3(self, k, n):
            res = []
            self.sum_help(k, n, 1, [], res)
            return res
    
        def sum_help(self, k, n, curr, arr, res, curr_sum=0):
            if len(arr) == k:
                if curr_sum == n:
                    res.append(arr[:])
                return
            if curr_sum >= n:
                return
    
            for i in xrange(curr, 10):
                arr.append(i)
                self.sum_help(k, n, i + 1, arr, res, curr_sum + i)
                arr.pop()
    

  • 0
    L

    @youke said in Concise python solution using DFS:

    res.append(list(arr))

    In the statement above

    If I remove "list", I get a wrong result.

    Why??


Log in to reply
 

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