Python DP solution with earlier termination

  • 0

    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]
            return comb[target]

Log in to reply

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