377. Combination Sum IV

377. Combination Sum IV

 

https://youtu.be/dw2nMCxG0ik?si=yplgrcGvhUBBlT9w

 

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # bottom-up dp        
        # nums = [num1, num2, num3, ...]
        # dp[0] = 1
        # dp[1] = ?
        # dp[2] = ?
        # dp[3] = ?
        # dp[target] = dp[target-num1] + dp[target-num2] + dp[target-num3] + ... 
        dp = {0:1}

        for total in range(1, target+1):
            dp[total] = 0 # init

            for n in nums:
                # dp[total-n] 이 없으면, 0으로..
                # 그래서, 특히, total-n 이 음수이면, 모두 0이 더해짐
                dp[total] += dp.get(total-n, 0) 

        return dp[target]