(Leetcode) 377 - Combination Sum IV

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.

https://leetcode.com/problems/combination-sum-iv/

dp 문제이다.

내가 푼 방식

from typing import List


class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)

        for i in range(1, target + 1):
            for num in nums:
                if i == num:
                    dp[i] += 1
                elif i > num:
                    subtract = i - num
                    dp[i] += dp[subtract]

        return int(dp[-1])

오히려 너무 어렵게 생각해서 시간이 좀 더 걸렸다.

예시로 nums = [1,2,3], target = 4 인 상황을 생각해보자.

dp의 각 값을 그 수일 때의 조합의 수 라고 해보자

• dp[1] : 1 - 1
• dp[2] : 2 - (1,1) 2
• dp[3] : 4 - (1,1,1) (2,1) (1,2) 3
• dp[4] : 7 - (1,1,1,1) (2,1,1) (1,2,1) (1,1,2) (2,2) (3,1) (1,3)

nums에 해당 값이 있을 때는 조합 없이 그 수만 사용해서 target을 구성할 수 있다. 따라서 바로 1을 추가해준다. (dp[i] += 1)

그 외의 경우에는 nums를 iterate 하면서 체크를 해보면 되는데

예를들어 dp[4]에서

• 1을 선택했을때는 dp[3] 에서 나온 조합에 1을 붙이는 것이고
  • (1,1,1) -> (1,1,1,1)
  • (2,1) -> (2,1,1)
  • (1,2) -> (1,2,1)
  • 3 -> (3,1)
• 2를 선택했을때는 dp[2] 에서 나온 조합에 2를 붙이는 것이고
  • (1,1) -> (1,1,2)
  • 2 -> (2,2)
• 3를 선택했을때는 dp[1] 에서 나온 조합에 3를 붙이는 것이다
  • 1 -> (1,3)

여기서 포인트는 뒤에 숫자를 추가한다고 combination의 수가 증가하지는 않는다.

따라서 dp[4] = dp[4-1] + dp[4-2] + dp[4-3] = dp[3] + dp[2] + dp[1] 이 되는것이다.