[Medium] 494. 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.

Examples

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 equal to 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: Dynamic Programming (Subset Sum)

Time Complexity: O(n × sum)
Space Complexity: O(sum)

Convert the problem to a subset sum problem using mathematical transformation.

class Solution:

    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        totalSum = sum(nums)
        
        # Check if target is achievable
        if (target + totalSum) % 2 != 0 or abs(target) > totalSum:
            return 0
        
        subsetSum = (target + totalSum) // 2
        dp = [0] * (subsetSum + 1)
        dp[0] = 1
        
        for num in nums:
            for i in range(subsetSum, num - 1, -1):
                dp[i] += dp[i - num]
        
        return dp[subsetSum]

How the Algorithm Works

Mathematical Transformation

The key insight is to transform the problem into a subset sum problem:

  1. Original Problem: Find ways to assign + or - to each number
  2. Transformation: Let S+ be the sum of numbers with + and S- be the sum of numbers with -
  3. Equations:
    • S+ - S- = target
    • S+ + S- = totalSum
  4. Solving: S+ = (target + totalSum) / 2

Step-by-Step Example: nums = [1,1,1,1,1], target = 3

Step Calculation Value
1 totalSum = 1+1+1+1+1 5
2 subsetSum = (3+5)/2 4
3 Find ways to make sum 4 5 ways

DP Table for subsetSum = 4:

nums = [1,1,1,1,1], target subsetSum = 4

Initial: dp = [1,0,0,0,0]

After num=1: dp = [1,1,0,0,0]
After num=1: dp = [1,2,1,0,0]  
After num=1: dp = [1,3,3,1,0]
After num=1: dp = [1,4,6,4,1]
After num=1: dp = [1,5,10,10,5]

Answer: dp[4] = 5

Visual Representation

Original Problem: [1,1,1,1,1] with target = 3

Possible combinations:
+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  ✓

Total: 5 ways

Algorithm Breakdown

1. Validation Check

if((target + totalSum) % 2 != 0 || abs(target) > totalSum) {
    return 0;
}

Why this check?

  • If (target + totalSum) is odd, subsetSum would be fractional (impossible)
  • If abs(target) > totalSum, it’s impossible to achieve the target

2. Subset Sum Calculation

int subsetSum = (target + totalSum) / 2;

Mathematical proof:

  • S+ - S- = target (equation 1)
  • S+ + S- = totalSum (equation 2)
  • Adding equations: 2S+ = target + totalSum
  • Therefore: S+ = (target + totalSum) / 2

3. DP Array Initialization

list[int] dp(subsetSum + 1, 0);
dp[0] = 1;  // One way to make sum 0 (empty subset)

4. Bottom-Up DP

for num in nums:
    for i in range(subsetSum, num - 1, -1):
        dp[i] += dp[i - num]

Why iterate backwards?

  • Prevents using the same number twice in one iteration
  • Ensures we only use numbers from previous iterations

Alternative Approaches

Approach 1: Brute Force (DFS)

class Solution:

    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        return self.dfs(nums, 0, target)
    
    def dfs(self, nums: list[int], index: int, target: int) -> int:
        if index == len(nums):
            return 1 if target == 0 else 0
        
        return (self.dfs(nums, index + 1, target - nums[index]) +
                self.dfs(nums, index + 1, target + nums[index]))

Time Complexity: O(2^n)
Space Complexity: O(n)

Approach 2: Memoization

class Solution:

    def findTargetSumWays(self, list[int] nums, int target) -> int:
        unordered_map<string, int> memo;
        return dfs(nums, 0, target, memo);
    }
    
    def dfs(self, nums: list[int], index: int, target: int, memo: dict) -> int:
        if index == len(nums):
            return 1 if target == 0 else 0
        
        key = f"{index},{target}"
        if key in memo:
            return memo[key]
        
        result = (self.dfs(nums, index + 1, target - nums[index], memo) +
                  self.dfs(nums, index + 1, target + nums[index], memo))
        
        memo[key] = result
        return result

Time Complexity: O(n × sum)
Space Complexity: O(n × sum)

Complexity Analysis

Approach Time Complexity Space Complexity
Brute Force O(2^n) O(n)
Memoization O(n × sum) O(n × sum)
DP (Subset Sum) O(n × sum) O(sum)

Edge Cases

  1. Impossible target: nums = [1], target = 2 → 0
  2. Single element: nums = [1], target = 1 → 1
  3. Zero target: nums = [1,1], target = 0 → 2
  4. Large numbers: nums = [1000], target = 1000 → 1

Key Insights

  1. Mathematical Transformation: Convert to subset sum problem
  2. DP Optimization: Use 1D array instead of 2D
  3. Backward Iteration: Prevents double counting
  4. Early Validation: Check feasibility before computation

Common Mistakes

  1. Forgetting validation: Not checking if target is achievable
  2. Wrong iteration order: Using forward iteration in DP
  3. Incorrect subset sum formula: Wrong calculation of subsetSum
  4. Array bounds: Not handling edge cases properly

Why This Solution is Optimal

  1. Mathematical Insight: Transforms exponential problem to polynomial
  2. Space Efficient: Uses 1D DP array instead of 2D
  3. Early Termination: Validates feasibility before computation
  4. Optimal Complexity: O(n × sum) is the best possible for this problem