{x}
blog image

Target Sum

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 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 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
+1 + 1 + 1 + 1 - 1 = 3

Example 2:

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 Explanation for LeetCode 494: Target Sum

This problem asks to find the number of ways to assign either '+' or '-' to each element in a given integer array nums such that the resulting sum equals a given target.

Core Idea: The problem can be elegantly reframed using a simple algebraic manipulation. Let's say S is the sum of all elements in nums. If we assign '+' to some elements and '-' to others, the resulting sum can be expressed as:

(Sum of elements with '+') - (Sum of elements with '-') = target

Let P represent the sum of elements with '+' and N represent the sum of elements with '-'. Then:

P - N = target

We also know that:

P + N = S (the sum of all elements)

Adding the two equations gives:

2P = target + S

P = (target + S) / 2

This implies that if target + S is odd or S < target, there's no solution (we can't have a fractional number of elements). If a solution exists, it boils down to finding the number of ways to select elements from nums that sum up to P.

This subproblem is a classic combinatorial problem that can be solved efficiently using dynamic programming.

Solution 1: Dynamic Programming (2D)

This approach uses a 2D array dp where dp[i][j] represents the number of ways to obtain a sum j using the first i elements of nums.

State Transition: For each element nums[i], we have two choices: include it (adding its value) or exclude it. Thus:

dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i]] (if j >= nums[i])

The base case is dp[0][0] = 1 (there's one way to get a sum of 0 using no elements).

Time Complexity: O(len(nums) * sum(nums)) - because the dp table has dimensions proportional to the length of the input array and the sum of its elements.

Space Complexity: O(len(nums) * sum(nums)) - for the 2D dp array.

Solution 2: Dynamic Programming (1D) - Space Optimization

We can optimize space by observing that each row in the dp table only depends on the previous row. Hence, we can reduce the dp array to a 1D array, iterating backwards to avoid overwriting values needed in the current iteration.

Time Complexity: O(len(nums) * sum(nums)) - remains the same as the algorithm still iterates through all the combinations.

Space Complexity: O(sum(nums)) - significantly reduced to a single 1D array.

Code Examples (Python)

Solution 1 (2D DP):

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        if (s - target) % 2 != 0 or s < target:
            return 0
        p = (s + target) // 2
        n = len(nums)
        dp = [[0] * (p + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(1, n + 1):
            for j in range(p + 1):
                dp[i][j] = dp[i - 1][j]
                if j >= nums[i - 1]:
                    dp[i][j] += dp[i - 1][j - nums[i - 1]]
        return dp[n][p]
 

Solution 2 (1D DP):

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        if (s - target) % 2 != 0 or s < target:
            return 0
        p = (s + target) // 2
        dp = [0] * (p + 1)
        dp[0] = 1
        for num in nums:
            for j in range(p, num - 1, -1):
                dp[j] += dp[j - num]
        return dp[p]

Both solutions achieve the same result, but the second one is more memory-efficient. The code in other languages would follow similar logic, adapting the syntax accordingly.