494. Target Sum

Problem Statement

link: LeetCode.cn LeetCode You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols ‘+’ and ‘-‘ before each integer in nums and then concatenate all the integers.

For example, if nums = [2, 1], you can add a ‘+’ before 2 and a ‘-‘ before 1 and concatenate them to build the expression “+2-1”. Return the number of different expressions that you can build, which evaluates to target.

Example:

Input: nums = [1,1,1,1,1], target = 3 Output: 5

Input: nums = [1], target = 1 Output: 1

Constraints: 1 <= nums.length <= 20 0 <= nums[i] <= 1000 0 <= sum(nums[i]) <= 1000 -1000 <= target <= 1000

Solution Approach

For the first solution (DFS), you are using Depth-First Search to explore all possible ways to add or subtract the elements in nums to reach the target sum.

For the second solution (DP), you are using Dynamic Programming to efficiently count the number of ways to reach the target sum by updating possible sums as you iterate through nums.

Algorithm

DFS Method

Recursive Exploration: Use a recursive function (dfs) to explore all possible ways of adding or subtracting each number in nums starting from the initial position. Base Case Check: When you reach the end of the nums list, check if the accumulated sum (curr) matches the target. If so, increment the result count. Recursive Calls: For each element, make two recursive calls: one where you add the current number and one where you subtract it.

DP Method

Initialization: Create a DP array dp to track the number of ways to achieve each possible sum, initialized with base values for the first element in nums. DP Transition: Iterate over each number in nums and update the DP array to reflect the new number of ways to achieve each sum by adding or subtracting the current number. Result Extraction: After processing all numbers, the value at the index corresponding to the target sum in the DP array represents the number of ways to achieve the target.

Complexity

DFS: Time complexity 𝑂(2^𝑛) and space complexity 𝑂(𝑛+2^𝑛). DP: Time complexity 𝑂(𝑛×sum(nums)) and space complexity 𝑂(sum(nums)).

Implement

    class Solution:
  def findTargetSumWays(self, nums: List[int], target: int) -> int:
      self.res = 0
      self.dfs(nums, 0, target, 0)
      return self.res
  def dfs(self, nums, start, target, curr):
      if start== len(nums):
          if target == curr:
              self.res += 1
          return 
      
      self.dfs(nums, start + 1, target, curr + nums[start])
      self.dfs(nums, start + 1, target, curr - nums[start])

  def findTargetSumWays(self, nums, target):
      _sum = sum(nums)
      if target < -_sum or target > _sum:
          return 0
      dp = [0] * (2 * _sum + 1)
      dp[nums[0] + _sum] = 1
      dp[-nums[0] + _sum] += 1

      for i in range(1, len(nums)):
          _next = [0] * (2 * _sum + 1)
          for s in range(2 * _sum + 1):
              if dp[s] > 0:
                  _next[s + nums[i]] += dp[s]
                  _next[s - nums[i]] += dp[s]
          dp = _next
      return dp[target + _sum]

    
    

Twitter  facebook  Email