[DP: 0 / 1 Knapsack] 494. Target Sum ★★★

494. Target Sum

 

이번엔 **합이 target이 되는 방법의 "개수"**를 구해야 해요.
즉, +num 또는 -num을 각각 선택해서 총 몇 가지 방법으로 target을 만들 수 있느냐가 핵심이에요.

---

✅ 핵심 아이디어: Subset Sum → 0/1 Knapsack

📌 문제를 수학적으로 바꿔보자:

우리가 각 숫자 앞에 + 또는 -를 붙이는데,
이를 두 그룹으로 나눠서:

• P: 더하는 숫자들의 합
• N: 빼는 숫자들의 합

라고 하면,

타겟 target = P - N

전체 합 total = P + N

두 식을 더하면: 2P = total + target
                        ⇒ P = (total + target) // 2

---

✅ 조건

• (total + target)이 짝수여야 함
• 그렇지 않으면 P가 정수가 아니므로 return 0

---

✅ 최종 문제로 변환됨:

nums 배열 중에서, 합이 P인 부분집합의 개수를 구하라

→ 이건 전형적인 0/1 Knapsack (합이 target인 subset 개수) 문제입니다.

 

from typing import List

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # P: 더해지는 숫자들의 합, N: 빼지는 숫자들의 합
        # P - N = target, P + N = total
        # => 2P = total + target → P = (target + total) // 2
        # 따라서, target + total 는 반드시 짝수여야 나눌 수 있음

        total = sum(nums)  # 전체 원소 합

        # target 이 너무 -값이어서, P가 음수일 수도 있음 → 이때는 불가능하므로 필터링해야 함
        # 예: target = -100, total = 5 → P = (5 + (-100)) // 2 = -47 ❌
        if (total + target) % 2 != 0 or abs(target) > total:
            return 0  # 홀수거나 불가능한 경우는 방법 없음

        P = (total + target) // 2  # 목표: 부분집합의 합이 정확히 P인 경우의 수를 구함

        # ✅ dp[t]: 합이 t가 되는 부분집합의 "경우의 수"
        # dp[0] = 1인 이유: 아무것도 선택하지 않는 공집합 하나가 존재 (합이 0)
        dp = [0] * (P + 1)
        dp[0] = 1

        # nums 배열의 각 숫자를 하나씩 보며 dp 배열을 업데이트
        for num in nums:
            # 역순으로 순회해야 같은 num을 여러 번 사용하는 것을 방지함 (0/1 Knapsack 방식)
            # dp[t - num] 값을 기반으로 dp[t]를 만들어야 하므로, 값이 덮이기 전에 순회함
            for t in range(P, num - 1, -1):
                # 현재 숫자 num을 사용해서, t를 만들 수 있는 방법을 누적
                # 이전에 합이 (t - num)인 방법이 존재하면,
                # 거기에 num을 추가하면 t가 되므로 그 개수를 dp[t]에 더함
                dp[t] += dp[t - num]

        # 최종적으로 합이 P가 되는 경우의 수가 우리가 찾는 정답
        return dp[P]

🧠 핵심 주석 요약

• dp[t]: 합이 t가 되는 부분집합의 "경우의 수"
• dp[t] += dp[t - num]: 이전 합에서 num을 추가해서 t를 만들 수 있는 경우를 누적
• dp[0] = 1: 아무것도 선택하지 않는 공집합도 유효한 경우 1개
• for t in range(P, num-1, -1): 역순으로 순회해야 이전 값이 덮이지 않음 (0/1 배낭 원리)

✅ DFS + Memoization 코드

from typing import List
from functools import lru_cache

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)

        # ✅ DFS(i, curr_sum): i번째 숫자까지 고려했을 때, 현재까지의 합이 curr_sum인 경우의 수
        @lru_cache(None)  # 같은 (i, curr_sum)에 대해 중복 계산 방지 (memoization)
        def dfs(i, curr_sum):
            if i == n:
                # 끝까지 도달했을 때, 원하는 합이 되었으면 1, 아니면 0
                return 1 if curr_sum == target else 0
            
            # 현재 숫자를 + 또는 - 로 사용해서 다음 단계로 진행
            add = dfs(i + 1, curr_sum + nums[i])
            subtract = dfs(i + 1, curr_sum - nums[i])
            return add + subtract  # 두 경우의 수를 더함

        return dfs(0, 0)  # 초기에는 0번째부터, 누적합도 0부터 시작

✅ 요약 비교

방식	특징	시간복잡도	공간복잡도	장점
DP (Bottom-up)	Subset sum 변형	O(n * sum)	O(sum)	빠름, 최적화
DFS + Memoization	완전탐색 + 캐싱	O(n * sum)	O(n * sum)	구조 직관적, 유연

https://youtu.be/dwMOrl85Xes

 

내 코드

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # 각 단계마다 + 아니면 - 선택해서 더하게 하면..

        res = [0] # 결과 counting

        def dfs(i, curSum):
            if i == len(nums):
                if curSum == target:
                    res[0] +=1
                return 

            dfs(i+1, curSum+nums[i])
            dfs(i+1, curSum-nums[i])

        dfs(0, 0)
        return res[0]

로직은 맞지만, 시간 제한 !!에 걸림

"DP+메모이제이션"으로 해결

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # 방법2: DFS + 메모이제이션(DP)을 활용한 풀이

        dp = {}  # 메모이제이션용 딕셔너리: key = (i, curSum), value = 경우의 수

        def dfs(i, curSum):
            """
            i번째 인덱스부터 시작해서, 현재까지의 합이 curSum일 때
            남은 숫자들로 target을 만들 수 있는 경우의 수를 반환하는 함수
            """

            # 종료 조건: 모든 숫자를 다 사용한 경우
            if i == len(nums):
                # 현재까지의 합이 target과 같으면 1가지 경우로 인정
                if curSum == target:
                    return 1
                else:
                    return 0  # 아니라면 경우의 수는 없음

            # 이미 계산한 (i, curSum)에 대해 결과가 있으면 바로 반환
            if (i, curSum) in dp:
                return dp[(i, curSum)]

            # 현재 숫자를 +로 사용한 경우의 수
            add = dfs(i + 1, curSum + nums[i])
            # 현재 숫자를 -로 사용한 경우의 수
            minus = dfs(i + 1, curSum - nums[i])

            # 현재 상태의 결과는 두 가지 경우의 수의 합
            dp[(i, curSum)] = add + minus

            return dp[(i, curSum)]  # 현재 상태의 경우의 수 반환

        # 0번째 인덱스부터 시작, 현재 합은 0으로 시작
        return dfs(0, 0)