LeetCode 494. Target Sum - 파이썬

문제 설명

nums 정수형 integer array가 주어졌을 때, nums의 각 숫자 앞에 +/- 기호를 붙인 뒤 연산을 통해 target 값을 만들 수 있는 수식의 가짓수를 반환해야 한다.

# 예시
Input: nums = [1,1,1,1,1], target = 3
Output: 5
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

문제 출처: https://leetcode.com/problems/target-sum/description/

문제 풀이

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        cache = dict() # (nums_index, calculation result) -> number of ways which evaluate to 'target'.

        def backtrack(index, calc_res):
        	# nums 배열의 끝 index를 넘었을 때, target 값과 같다면 1 반환.
            if index == len(nums):
                return 1 if calc_res == target else 0
			
            # cache에 이미 동일한 계산 결과가 존재한다면, cache에 저장된 값 반환.
            if (index, calc_res) in cache:
                return cache[(index, calc_res)]
			
            # +/- 각각의 연산 결과를 backtracking한다.
            cache[(index, calc_res)] = backtrack(index + 1, calc_res + nums[index]) + backtrack(index + 1, calc_res - nums[index])

            return cache[(index, calc_res)]

        return backtrack(0, 0)

# cache 예시
{(4, 4): 1, (4, 2): 1, (3, 3): 2, (4, 0): 0, (3, 1): 1, (2, 2): 3, (4, -2): 0, (3, -1): 0, (2, 0): 1, (1, 1): 4}