Leetcode # 494. Target Sum

Problem

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

First Try
[Time Limit Exceeded  124 / 140 testcases passed]

Time Complexity: O(2 ** len(nums))
Space Complexity: O(2 ** len(nums))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def findTargetSumWays(self, nums: List[int], target: int) -> int:
    rest_sum = [nums[-1]] * (len(nums) - 1)
    for i in range(len(rest_sum) - 2, -1, -1):
      rest_sum[i] = nums[i + 1] + rest_sum[i + 1]

    expressions_n = 0
    queue = deque([[0, 0]])
    while queue:
      i, pre_sum = queue.popleft()
      for symbol in [1, -1]:
        cur_sum = pre_sum + symbol * nums[i]
        if i == len(nums) - 1:
          if cur_sum == target:
            expressions_n += 1
          continue

        # 打ち切り法
        distance = abs(cur_sum - target)
        if (distance - rest_sum[i]) * (1 if distance >= 0 else -1) > 0: continue

        queue.append([i + 1, cur_sum])
    
    return expressions_n

Solution: Tabulation

Time Complexity: O(len(nums) * sum(nums))
Space Complexity: O(len(nums) * sum(nums))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def findTargetSumWays(self, nums: List[int], target: int) -> int:
    ans = defaultdict(Counter)
    ans[len(nums) - 1][ nums[-1]] += 1
    ans[len(nums) - 1][-nums[-1]] += 1
    for i in range(len(nums) - 2, -1, -1):
      for n in ans[i + 1]:
        ans[i][n + nums[i]] += ans[i + 1][n]
        ans[i][n - nums[i]] += ans[i + 1][n]
    return ans[0][target]

Solution: Tabulation (Optimized Space Complexity)

Time Complexity: O(len(nums) * sum(nums))
Space Complexity: O(len(nums) * sum(nums))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def findTargetSumWays(self, nums: List[int], target: int) -> int:
    pre = Counter([nums[-1], -nums[-1]])
    for i in range(len(nums) - 1):
      cur = Counter()
      for n in pre:
        cur[n + nums[i]] += pre[n]
        cur[n - nums[i]] += pre[n]
      pre = cur
    return pre[target]

Last Updated on 2024/12/26 by A1go