(Python3) - LeetCode (Medium) : 494. Target Sum

https://leetcode.com/problems/target-sum

memoization을 활용한 dfs문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. 변수 depth선언 후 nums의 길이를 저장합니다.

 

2.(각 depth별 만들어진 숫자를 key로), 만드는 경우의 수를 value로 hash map인 memo를 선언 후 빈 객체로 초기화합니다.

📔 풀이과정

문제는 중복 상태를 메모이제이션으로 방지하며 재귀 호출을 최적화하는 방식으로 해결할 수 있습니다. nums 배열의 길이가 최대 20이며 각 원소는 1000 이하, 합계는 -20,000 ~ 20,000 범위를 가지므로 ${( n \cdot S = 20 \cdot 40,001 \approx 800,000 )}$번의 계산으로 해결 가능합니다.

풀이 과정은 다음과 같습니다:

1. 기저 조건
   깊이 \( n \)이 nums 배열의 길이와 같아지면, 현재 합계 ( num )이 목표 값 ( target )인지 확인합니다. 같다면 1, 아니면 0을 반환합니다.

2. 중복 상태 확인:  
   메모 테이블 `memo`에 현재 상태 (n, num)가 이미 계산되어 있다면, 재귀 호출을 생략하고 해당 값을 반환합니다.

3. 재귀 호출:  
   계산되지 않은 깊이와 상태에 대해, 현재 `nums[n]`를 더하거나 뺀 두 가지 경우를 각각 재귀 호출합니다. 이때 반환값을 더한 결과가 현재 상태를 만들기 위한 경우의 수가 되며, 이를 `memo`에 저장합니다.

4. 결과 반환:  
   갱신된 메모 값을 반환합니다.

최적화된 재귀 호출을 통해 시간 복잡도와 공간 복잡도를 모두 ${( O(n \cdot S) )}$로 줄일 수 있습니다.

📔 정답 출력 | 반환

dfs에 깊이 0, 값 0을 인자로 넘겨 계산한 값을 반환합니다.

---

📕 Code

📔 Python3

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        depth = len(nums)
        memo = {}
        def dfs(n: int, num: int):
            if n == depth:
                if num == target:
                    return 1
                return 0
            if (n, num) in memo:
                return memo[(n, num)]
            memo[(n,num)] = dfs(n + 1, num + nums[n]) + dfs(n+1, num - nums[n])
            
            return memo[(n,num)]
        return dfs(0, 0)

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.