Python DP Solution - 48ms


  • 0
    H

    The idea is - If target is 10, find the number of ways to reach 10 - nums[0], 10 - nums[1], ... and add them up. And do this in a bottom up way.

        def combinationSum4(self, nums, target):
            arr = [0 for i in range(target + 1)]
            arr[0] = 1    # for DP base case
            nums = set(nums)    # don't want to consider duplicates
            for i in range(len(arr)):
                if (arr[i] == 0):    # no way to reach this target, so skip
                    continue
                for num in nums:
                    if (i + num <= target):
                        arr[i + num] += arr[i]
                        
            return arr[-1]
    

Log in to reply
 

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