LeetCode 筆記 - 377. Combination Sum IV

class Solution:
    def combinationSum4(self, candidates: List[int], target: int) -> int:
        
        candidates = [n for n in candidates if n <= target]
        candidates.sort()
        
        dp = collections.defaultdict(int)
        
        for i in range(1, target + 1):
            for c in candidates:
                if c > i:
                    break
                    
                if c == i:
                    dp[i] += 1
                else:
                    dp[i] += dp[i - c]
        
        return dp[target]