2023-09-09 07:20:26 +0000 UTC

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:

        @cache
        def backtrack(cur_sum: int) -> int:
            if cur_sum == target:
                return 1
            if cur_sum > target:
                return 0
            
            return sum(backtrack(cur_sum + num) for num in nums)

        return backtrack(0)