Leetcode 494. Target Sum

Let's understand what we're being asked to do. We have an array like nums = [1, 1, 1, 1, 1] and a target = 3. We need to count how many ways we can assign + or - signs to each element so the sum equals the target.

For example: +1 +1 +1 +1 +1 = 5 (not our target), but +1 -1 +1 -1 +1 = 1 (also not our target), and +1 +1 +1 -1 -1 = 1 (still not our target). However, +1 +1 +1 +1 -1 = 3 works! We need to count ALL such valid assignments.

Key insight from the problem: This can be transformed into a subset-sum problem. If we choose some elements to be positive (call their sum P) and the rest to be negative (call their sum N), then P - N = target and P + N = sum(nums). Solving these equations: P = (sum(nums) + target) / 2. So we need to count subsets that sum to this value.

Important constraints: The value (sum(nums) + target) / 2 must be an integer and non-negative for a solution to exist. If sum(nums) + target is odd, or if target > sum(nums), there are zero ways.

Edge cases to consider: What if nums contains zeros? (Each zero doubles the number of ways since it can be +0 or -0). What if target is negative? What if the array is empty?

The brute force approach tries all possible sign assignments using recursive backtracking. For each element, we recursively explore two branches: adding it with a + sign or with a - sign. When we reach the end of the array, we check if the current sum equals the target and increment our count if it does. This explores all 2^n possible combinations of signs.

def target_sum_ways(nums, target):
    """
    Count ways to assign +/- to each element so signed sum equals target.
    Brute force: try all 2^n sign combinations using backtracking.
    """
    count = 0
    
    def backtrack(index, current_sum):
        nonlocal count
        
        # Base case: reached end of array
        if index == len(nums):
            if current_sum == target:
                count += 1
            return
        
        # Recursive case: try adding with + sign
        backtrack(index + 1, current_sum + nums[index])
        
        # Recursive case: try adding with - sign
        backtrack(index + 1, current_sum - nums[index])
    
    # Start backtracking from index 0 with sum 0
    backtrack(0, 0)
    
    return count

Instead of thinking about assigning signs to each element, think about partitioning the array into two groups: elements that will be positive and elements that will be negative.

If the positive group sums to P and the negative group sums to N, then our signed sum is P - N = target. We also know P + N = sum(nums) (total of all elements). Solving these two equations gives us P = (sum(nums) + target) / 2.

This transforms the problem: count how many subsets of nums sum to exactly P.

The subset-sum counting problem is a classic dynamic programming problem with well-known solutions.

By recognizing this transformation, we convert a seemingly complex "sign assignment" problem into a standard DP pattern. This is much easier to solve efficiently than trying all 2^n possible sign combinations!

Imagine you have coins [1, 1, 1, 1, 1] and need to reach target = 3. Instead of thinking "which coins get + and which get -", think "which coins do I pick for the positive pile?"

If you pick three coins for the positive pile (sum = 3), the remaining two go to the negative pile (sum = 2). The signed sum is 3 - 2 = 1 (not our target).

If you pick four coins for the positive pile (sum = 4), the remaining one goes to the negative pile (sum = 1). The signed sum is 4 - 1 = 3 (our target!).

So we need to count: how many ways can we pick a subset that sums to 4? This is the subset-sum counting problem, which we can solve with dynamic programming by building up counts for each possible sum.

The optimal approach first transforms the problem into subset-sum: calculate P = (sum(nums) + target) / 2 and count subsets that sum to P. If (sum(nums) + target) is odd or negative, return 0. Use dynamic programming with a 1D array dp where dp[i] represents the number of ways to achieve sum i. Initialize dp[0] = 1 (one way to make sum 0: pick nothing). For each number in nums, update the dp array by iterating backwards from P to num, adding dp[j - num] to dp[j]. The answer is dp[P].

def target_sum_ways(nums, target):
    """
    Count ways to assign +/- to each element so signed sum equals target.
    Transform to subset-sum: count subsets with sum P = (sum(nums) + target) / 2.
    """
    # Calculate total sum and target subset sum P
    total_sum = sum(nums)
    
    # Check if transformation is valid
    if (total_sum + target) % 2 != 0:
        return 0
    
    if total_sum < abs(target):
        return 0
    
    P = (total_sum + target) // 2
    
    # Initialize DP array: dp[i] = number of ways to achieve sum i
    dp = [0] * (P + 1)
    dp[0] = 1  # One way to make sum 0: pick nothing
    
    # Process each number in nums
    for num in nums:
        # Iterate backwards from P to num to avoid using same element twice
        for j in range(P, num - 1, -1):
            # Add ways to achieve sum (j - num) to ways to achieve sum j
            dp[j] += dp[j - num]
    
    # Return number of ways to achieve sum P
    return dp[P]

• Problem transformation insight: When you see "assign +/− to elements to reach a target", recognize this transforms into a subset-sum problem. If subset P gets '+' and subset N gets '−', then sum(P) − sum(N) = target and sum(P) + sum(N) = sum(nums), solving gives sum(P) = (sum(nums) + target) / 2. This reduction converts a complex assignment problem into standard DP.
• Parity and feasibility checks: Before attempting DP, validate that (sum(nums) + target) is even and non-negative - if odd, no solution exists since we're dividing by 2 to find integer subset sums. Also check |target| ≤ sum(nums), otherwise the target is unreachable. These O(1) checks prevent unnecessary computation.
• 1D DP space optimization: Use a single array dp[i] = count of ways to sum to i, iterating backwards (right to left) when updating to avoid using already-modified values from the current iteration. This reduces space from O(n × capacity) to O(capacity) while maintaining correctness, critical when capacity = (sum + target) / 2 is large.
• Zero-initialization pattern: Initialize dp[0] = 1 (one way to make sum 0: select nothing) and all other dp[i] = 0. For each number, update dp[j] += dp[j − num] for all valid j, accumulating counts. The final answer is dp[target_sum], representing all combinations that sum to the transformed target.
• Combinatorial DP recurrence: The transition dp[j] += dp[j − num] embodies the principle that ways to make sum j equals ways without current number plus ways to make (j − num) then add num. This additive counting pattern applies to all "count number of ways" subset problems, distinct from "find minimum/maximum" which uses min/max.
• Partition and balance problems: This +/− assignment = subset partitioning pattern extends to problems like "Partition Equal Subset Sum", "Minimum Subset Sum Difference", and "Count of Subset Sum". Whenever you need to split an array into groups with sum constraints, consider transforming into a single subset-sum DP problem.