Leetcode 377 Combination Sum IV

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The answer is guaranteed to fit in a 32-bit integer.

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Input: nums = [9], target = 3
Output: 0

• Bu soruda bize liste olarak bir kaç sayı ve hedef(target) bir sayı veriliyor.
• Bu listedeki sayılar ile kaç farklı şekilde hedef sayı elde edilebilir diye soruluyor.
• Dp kullanarak bu soruyu çözebiliriz.
• Input: nums = [1,2,3], target = 4 için
• dp[0] = 1 başlayarak hedefteki sayıya gidebiliriz.
• dp[1] = dp[1-1] + dp[1-2] +dp[1-3] sondaki ikisi zaten olmaz 0 sadece ilk dp [1-1] = dp[0] = 1
• dp[2] = dp[2-1] + dp[2-2] +dp[2-3] sondaki olmaz 0 sadece ilk 2 durum için dp[1] + dp[0] = 2
• dp[3] = dp[3-1] + dp[3-2] +dp[2-3] -> dp[2] + dp[1] + dp [0] = 2+1+1=4
• dp[4] = dp[4-1] + dp[4-2] +dp[4-3] -> dp[3] + dp[2] + dp[1] = 4+2+1=7

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = {0:1}
        
        for total in range(1, target + 1):
            dp[total] = 0
            for n in nums:
                dp[total] += dp.get(total - n, 0)
        return dp[target]