[LC] 494. Target Sum

[seungriyou]

https://leetcode.com/problems/target-sum/ (similar to #71)

Approach

Idea 1: Backtracking + Memo

ref: https://leetcode.com/problems/target-sum/solutions/455024/dp-is-easy-5-steps-to-think-through-dp-questions

일반적인 backtracking을 시도하면 TLE가 발생한다. (한 번 호출 당 2번(pos, neg)의 호출 -> O(2^n))

따라서 결과를 memoization 하는 방법을 사용해야 하는데, 이를 위해서는 memo hash table을 사용하거나, @cache decorator를 사용하면 된다.

⬇️ backtracking에서 memo hash table을 사용하려면, 다음과 같은 구조로 사용하면 된다.

[!tip] memo의 index를 tuple로 사용하면 2D array를 가질 필요가 없다!

memo = {}

def backtrack(tot, idx):
    # from memo (resolve TLE)
    if (tot, idx) in memo:
        return memo[(tot, idx)]

    # base case
    if idx == n:
        if tot == target:
            return 1
        return 0

    # recur
    pos = backtrack(tot + nums[idx], idx + 1)
    neg = backtrack(tot - nums[idx], idx + 1)

    # memo
    memo[(tot, idx)] = pos + neg

    return memo[(tot, idx)]

[!note]

어떤 조건에 따라 개수를 세려면, cnt 값을 nonlocal 등으로 선언해서 트래킹하는 것보다 return 값을 이용하여 반환하는 편이 더 깔끔한 것 같다.

이렇게 하면, 두 가지 경우(+, -) 각각에 대해서 recursive 하게 호출한 후, 각각의 결과값을 더해야 한다는 것에 주의하자!

Idea 2: DP (2D -> 1D)

ref: https://leetcode.com/problems/target-sum/solutions/97343/python-dp, https://leetcode.com/problems/target-sum/editorial/

다음과 같이 2D DP로 풀 수 있다. (0/1 knapsack)

dp[i][j] = i번째 item까지 봤을 때 합이 j인 경우의 수

하지만 각 row는 이전 row(dp[i - 1])만 보기 때문에, 1D DP로 space optimize가 가능하다.

또한, list가 아닌 defaultdict로 관리하면 필요한 값만 저장할 수 있기 때문에 space 측면에서 더 이점을 볼 수 있을 것 같다. (근데 무조건 좋기만 할까..? list와 dict 모두 python에서는 O(1)에 접근가능하지만, 실제로 시간에 차이가 날 수도 있지 않을까)

이런 패턴은 기억해두자...!

def findTargetSumWays(self, nums: List[int], target: int) -> int:    
    from collections import defaultdict

    dp = defaultdict(int)
    dp[0] = 1   # base case

    for num in nums:
        tmp = defaultdict(int)
        for tot, cnt in dp.items():
            tmp[tot + num] += cnt
            tmp[tot - num] += cnt
        dp = tmp

    return dp[target]

img src

Complexity (?! - 다시 고민해봐야 할 듯)

n = len(nums), t = sum(nums), l = sum(nums)의 최댓값과 최솟값 간 차이

• Time:
  • (backtracking + memo) O(l * n) (memo가 단 한 번 채워짐)
  • (1D dp) O(l * n)
• Space:
  • (backtracking + memo) O(l * n) (memo, recursion stack)
  • (1D dp) O(l)