The idea is - If target is 10, find the number of ways to reach
10 - nums,
10 - nums, ... 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 = 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]