[Leetcode 494] Target Sum

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

1) 코드

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        
        memo = {}

        def bt(index, currentSum):
            if index == len(nums):
                return 1 if currentSum == target else 0

            if (index, currentSum) in memo:
                return memo[(index, currentSum)]

            addition = bt(index+1, currentSum + nums[index])
            subtraction = bt(index+1, currentSum - nums[index])

            memo[(index, currentSum)] = addition+subtraction

            return addition+subtraction 


        return bt(0, 0)

2) 해설

• DP+Backtracking을 결합하여 풀어야 하는 문제이며,
  DP를 통한 최적화가 중요한 문제이다.
• 여기서 의미하는 최적화는 memoization을 의미한다.
• 만약에 특정 인덱스까지 계산했을 때, 현재 합과 같은 합이
  이미 memoization되어 있다면,
  어차피 하위 케이스에 대해서 또 계산할 필요가 없다.
  왜냐면 어차피 그 갯수가 같기 때문이다.
• DP는 그림을 그려서 이해를 시도하는 것이
  좀 더 효과적인 것 같다.