[LeetCode] 494. Target Sum

Video Explanation

Table of Content

Problem Statement
Problem Input
Solution

Problem statement

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-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

There are 5 ways to assign symbols to make the sum of nums be target 3.

Constraints

The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

Input

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:

Brute force recursion

Source code

Time Complexity: O(2^N)

Space Complexity: O(N)

For every symbol in nums, we can make 2 choices, + or -. This naturally falls into a tree structure with 2 childrens per parent. In my approach, I deducted the choice from the target at each level of the tree. You can also introduce an extra variable to accumulate the running sum instead of deducting. If the path from the root of the tree to the leaf gives me a target of 0, I know I have successfully found a valid arrangement of choices to reach the target, so I can return 1. Else, it is invalid, so I return 0.

Base Case

At the end of nums if my remaining target is 0, return 1 for indicating a good path, 0 otherwise.

Recursion

Sum of paths from my negative choice and my positive choice at the current index.

![](../assets/leetcode-494-target-sum/tree.png)

Decision Tree

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
      return self.recursive(nums, 0, S)

    def recursive(self, nums, index, target):
      # base case
      if index >= len(nums):
        return 1 if target == 0 else 0

      # binary decisions
      # first choice = positive symbol, deduct from target
      # second choice = negative symbol, deduct from target
      return self.recursive(nums, index+1, target - nums[index]) + self.recursive(nums, index+1, target + nums[index])

Complexity Explanation

The time complexity is the number of leaf nodes in our tree, which is O(2^(N+1) or O(2^N). The space complexity is the depth of our tree, which is O(N+1) or O(N)

2D Dynamic Programming

Source code

Time Complexity: O(N*sum(nums))

Space Complexity: O(N*sum(nums))

Now I will show you how you can directly convert the above recursive approach into an iterative DP solution.

If you noticed, the above recursion approach has 2 variables that keeps on changing, index and target

The goal of the DP is to precompute a table of index and target, so that you can avoid keep branching on sub-problems that you have already solved in the decision tree. Refer to the red color nodes in the diagram above, those sub-problems are being solved more than once, so the table allows to fill in the answer for that sub-problem once and then we can access the solution as many times as we need to without having to re-solve it.

To do this, we need a 2D table consist of index and target values.

index should be straightforward as it comes straight from the nums array, so we only need up to its length.

target is a bit tricky. Using the given constraints of the problem, we can use 1000 since the sum of nums can not exceed 1000, a target > 1000 will never be possible. However, following the same logic, we can achieve the same constraint by just using sum of nums. So our target is limited from -sum(nums) -> sum(nums), -sum(nums) is for in case all symbols are negative. In code, I called this sum(nums), max_limit

Initializing DP table

When we generate our 2D DP table, we can initialize everything to 0 at first to indicate that there is currently 0 paths for the many combinations of index and target. Finally, we need to initialize the table with our base case. If we stay consistent with our recursive approach, we want to fill the equivalent of

 if index >= len(nums):
        return 1 if target == 0 else 0

in our table. We can do so by dp[n][0] = 1 because if we reached the end of nums and target is 0, it is a valid path.

BUT WAIT

Because our table represents negative values as well, e.g [-3,-2,-1, 0, 1, 2, 3], we need to shift our indices, so our indices don’t go out of bounds. We’ll map it by shifting it by max_limit, so it becomes within range of [0,1,2,3,4,5,6]. So we end up with dp[n][0+max_limit] = 1.

Filling the DP table

When we fill the table, we want to utilize our initialized values and gradually fill the rest of the table from there. Since we have filled dp[n][max_limit] with a useful value, we want to start filling starting from there.

      # iterate from n-1 -> 0
      for i in reversed(range(n)):
        for j in range(-max_limit, max_limit+1): # e.g, -3 -> 3, if max_limit was 3
          # TODO: recursion replacement here

Inside the TODO, we want to do the exact equivalent of

return self.recursive(nums, index+1, target - nums[index]) + self.recursive(nums, index+1, target + nums[index])

so then we have:

dp[i][j] = dp[i+1][j-nums[i] + dp[i+1][j+nums[i]], # j = target, i = index

See the similarity here? It is a direct translation.

BUT WAIT, WE ARE NOT DONE

Remember how we needed to shift dp[n][0]? We need to do the same here.

  centered_j = j + max_limit
  # replace j with centered_j
  dp[i][centered_j] = dp[i+1][centered_j-nums[i] + dp[i+1][centered_j+nums[i]], # j = target, i = index

Also because we are iterate through the entire -max_limit -> max_limit of our table, centered_j + nums[i] and centered_j - nums[i] can easily go out of bounds. However, we can ignore those cases because there is no way for us to reach a target that is outside of our limits. So we guard out of bounds access by if centered_j + nums[i] >= 0 and centered_j + nums[i] <= 2*max_limit: and vice versa for centered_j - nums[i] since our table indices for target runs from 0 to 2*max_limit+1.

So after modifying out code with the guard, we would have

    # Remember to shift :D
    centered_j = j + max_limit
    # Choosing a positive and deducting
    negative = centered_j - nums[i]
    # Choosing a negative and deducting
    positive = centered_j + nums[i]

    # it is possible for out of bounds, but we don't care because we know it is impossible to achieve a target that is outside of our limit
    if negative >= 0 and negative <= 2*max_limit:
      dp[i][centered_j] += dp[i+1][negative]
    if positive >= 0 and positive <= 2*max_limit:
      dp[i][centered_j] += dp[i+1][positive]

Finally, we finished filling up our DP table. Our answer will reside in the equivalent of

return self.recursive(nums, 0, target)

, which is dp[0][target+max_limit], shifted by max_limit.

We also need to add a guard for this in case, the target exceeds our limits again, so

return 0 if target < -max_limit or target > max_limit else dp[0][target + max_limit]

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
      return self.dp(nums, S)

    def dp(self, nums, target):
      n = len(nums)
      max_limit = sum(nums)

      dp = [[ 0 for i in range(max_limit*2+1) ] for j in range(n+1)]

      # Remember to shift by max_limit to move negative indices to correct indices
      dp[n][max_limit] = 1

      # iterate from n-1 -> 0
      for i in reversed(range(n)):
        for j in range(-max_limit, max_limit+1): # -3 -> 3, if limit was 3
          # Remember to shift :D
          centered_j = j + max_limit
          # Choosing a positive and deducting
          negative = centered_j - nums[i]
          # Choosing a negative and deducting
          positive = centered_j + nums[i]

          # it is possible for out of bounds, but we don't care because we know it is impossible to achieve a target that is outside of our limit
          if negative >= 0 and negative <= 2*max_limit:
            dp[i][centered_j] += dp[i+1][negative]
          if positive >= 0 and positive <= 2*max_limit:
            dp[i][centered_j] += dp[i+1][positive]

      # Remember to shift again :D
      return 0 if target < -max_limit or target > max_limit else dp[0][target + max_limit]