377. Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/

Python

Top Down DP

from functools import cache


class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        @cache
        def dp(remain):
            if remain == 0:
                return 1
            if remain < 0:
                return 0

            count = 0
            for num in nums:
                count += dp(remain-num)
            return count

        return dp(target)