[LeetCode] 377 | Combination Sum IV | Python

---

문제 링크: https://leetcode.com/problems/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 test cases are generated so that the answer can fit in a 32-bit integer.

---

조건

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• All the elements of nums are unique.
• 1 <= target <= 1000

---

내 풀이

Dynamic Programming을 이용해서 해결한다.

문제에서 주어진 예시처럼 nums=[1,2,3], target=4라 하자. 그럼 위와 같이 dp가 만들어진다.

---

먼저 nums로 합이 1이 되도록 만들 수 있는 경우를 생각해보자.

그 경우는 (1)로만 이루어진 경우다.

따라서 빨간색 글씨처럼 이루어진다.

---

nums로 합이 2가 되도록 만들 수 있는 경우를 생각해보자.

그 경우는 두 가지가 될 수 있다.

1에다 1을 더해서 2가 되는 경우, 0에다 2를 더해서 2가 되는 경우.

---

nums로 합이 3이 되도록 만들 수 있는 경우를 생각해보자.

그 경우는 세 가지가 될 수 있다.

2에다 1을 더해서 3이 되는 경우, 1에다 2를 더해서 3이 되는 경우, 0에다 3을 더해서 3이 되는 경우.

---

nums로 합이 4가 되도록 만들 수 있는 경우를 생각해보자.

그 경우는 세 가지가 될 수 있다.

3에다 1을 더해서 4가 되는 경우, 2에다 2를 더해서 4가 되는 경우, 1에다 3을 더해서 4가 되는 경우.

따라서 총 7가지의 경우가 된다.

 

위의 방법을 코드로 짜보면 아래 코드처럼 나온다.

---

코드

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target+1)
        dp[0] = 1
        
        for i in range(1, target+1):
            for num in nums:
                if num <= i:
                    dp[i] += dp[i-num]
        
        return dp[target]