Leetcode 377. Combination Sum IV

Problem

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Algorithm

Dynamics Programming (DP).

Code

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nlen = len(nums)
        ans = [0] * (target + 1)
        ans[0] = 1
        for v in range(target+1):
            for i in range(nlen):
                if v >= nums[i]:
                    ans[v] = ans[v] + ans[v-nums[i]]
        
        return ans[target]
1
2
3
4
5
6
7
8
9
10
11