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


class Solution:
    def _innerCS(self, nums: list[int], target: int, dp: dict) -> int:
        if target in dp:
            return dp[target]

        cnt = 0
        if target == 0:
            cnt = 1
        elif target < 0:
            cnt = 0
        else:
            for num in nums:
                if num > target:
                    break
                cnt += self._innerCS(nums, target - num, dp)

        if target >= 0:
            dp[target] = cnt
        return cnt

    def combinationSum4(self, nums: list[int], target: int) -> int:
        dp = {}
        nums.sort()
        return self._innerCS(nums, target, dp)

    def bottomUpApproach(self, nums: list[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for idx in range(1, target + 1):
            for num in nums:
                if idx >= num:
                    dp[idx] += dp[idx - num]
        return dp[target]


nums = [1, 2, 3]
target = 4
print(Solution().combinationSum4(nums, target))
# https://leetcode.com/problems/combination-sum-iv/


class Solution:
    def _innerCS(self, nums: list[int], target: int, dp: dict) -> int:
        if target in dp:
            return dp[target]

        cnt = 0
        if target == 0:
            cnt = 1
        elif target < 0:
            cnt = 0
        else:
            for num in nums:
                if num > target:
                    break
                cnt += self._innerCS(nums, target - num, dp)

        if target >= 0:
            dp[target] = cnt
        return cnt

    def combinationSum4(self, nums: list[int], target: int) -> int:
        dp = {}
        nums.sort()
        return self._innerCS(nums, target, dp)

    def bottomUpApproach(self, nums: list[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for idx in range(1, target + 1):
            for num in nums:
                if idx >= num:
                    dp[idx] += dp[idx - num]
        return dp[target]


nums = [1, 2, 3]
target = 4
print(Solution().combinationSum4(nums, target))
# https://leetcode.com/problems/combination-sum-iv/