Python DP solution with earlier termination


  • 0
    J

    Adding a sort can make the early termination from the inner loop safe, therefore improve the performance:

    class Solution(object):
    
        def combinationSum4(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            comb, nums = [1] + [0] * target, sorted(nums)
            for t in range(1, target + 1):
                for n in nums:
                    if t >= n:
                        comb[t] += comb[t - n]
                    else:
                        break
    
            return comb[target]
    

Log in to reply
 

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