Python DFS 39ms beat 85.62%


  • 0
    G

    Break the loop once current test num > n // k.
    for example, n = 9, k = 3

    1. suppose you find 1, 2, you do not need to test 7, 8,9. now n = 9 -1-2, k = 3 -1 -1. n//k = 6/1 = 6. 7,8,9 all these numbers are greater than 6
    2. suppose your first number is 3, then n = 9-3= 6, k = 2. all 4,5,6,7,8,9 can be dropped by the condition num > 6/2

    The return condition could be improved.

    class Solution(object):
        def combinationSum3(self, k, n):
            """
            :type k: int
            :type n: int
            :rtype: List[List[int]]
            """
            res = []
            self.dps(k, n, 1, [], res)
            return res
            
        def dps(self, k, n, next_num, temp, res):
            if k == 0:
                if n == 0: 
                    res.append(temp)
                return
            if n < k * next_num:
                return       
            for num in range(next_num, 10):
                if num > n / k:
                    break
                self.dps(k-1, n-num, num+1, temp + [num], res)

Log in to reply
 

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