Domain 2MediumCORE

Target Sum

We need to determine the number of ways to assign a + or - sign to each integer in an array such that their total sum equals a target value S.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming#Depth-first Search

494. Target Sum

Model: qwen3.5:9b
Topics: Dynamic Programming,Depth-first Search
FAANG asked: 1
Acceptance rate: 45.6%


Problem Breakdown

We need to determine the number of ways to assign a + or - sign to each integer in an array such that their total sum equals a target value S.

Inputs:

  • A list of non-negative integers (nums).
  • An integer target sum (S).

Outputs:

  • The count of valid assignments.

Constraints & Edge Cases:

  1. Non-negative Integers: All elements in nums are ≥0\ge 0. This is crucial because it allows us to treat the problem as a variation of the Subset Sum (Knapsack) problem rather than general partitioning with negatives.
  2. Array Length (N≤20N \le 20): While small enough for brute-force recursion, this hints that we should look for polynomial time solutions relative to SS.
  3. Sum Constraint: The sum of elements is ≤1000\le 1000. This bounds the state space significantly, making Dynamic Programming feasible and optimal (O(N⋅S)O(N \cdot S)).
  4. Impossible Targets: If |S| exceeds the total possible sum or if parity doesn’t match (sum + target must be even), no solution exists.

Intuition

A strong candidate starts by considering a brute-force approach: Depth-First Search (DFS) where we branch at each number, trying both adding and subtracting it from our running current sum.

Why Brute Force is Insufficient: This creates 2N2^N states. With N=20N=20, that’s roughly 10610^6 operations, which passes within time limits but doesn’t scale well if constraints were looser (e.g., standard LeetCode version often has larger sums). More importantly, many different paths in the DFS tree lead to the same intermediate sum at a specific index. We are recomputing work for overlapping subproblems.

Key Insight: Let PP be the set of numbers assigned + and MM be the set assigned -. We want: ∑P−∑M=S\sum P - \sum M = S. We also know that every number is used exactly once, so: ∑P+∑M=Total Sum(Σ)\sum P + \sum M = \text{Total Sum} (\Sigma).

If we add these two equations: (∑P−∑M)+(∑P+∑M)=2P(\sum P - \sum M) + (\sum P + \sum M) = 2P ⇒S+Σ=2P\Rightarrow S + \Sigma = 2P ⇒P=(S+Σ)/2\Rightarrow P = (S + \Sigma) / 2

This transforms the problem into finding how many subsets of nums sum up to exactly PP. This is a classic 0/1 Knapsack counting problem. We just need to count ways to form subset sum PP, and every valid way automatically implies the remaining numbers are assigned -.

Approach

We will use Dynamic Programming (DP) with space optimization, similar to the Subset Sum solution pattern.

  1. Calculate Total: Compute total_sum of all elements in nums.
  2. Feasibility Check:
    • If (S + total_sum) is odd or negative, return 0 immediately (since PP must be a non-negative integer). Note that if the sum difference has different parity than required for an even split (2P=total+S2P = \text{total} + S), no solution exists.
  3. Define Target Subset Sum (KK): Let K=(total_sum+S)/2K = (total\_sum + S) / 2. We need to find the number of subsets that sum exactly to KK.
  4. DP Initialization: Create an array dp where index represents a possible subset sum, and value represents the count of ways to achieve it. Initialize dp[0] = 1 (one way to get sum 0: pick nothing). All other indices are 0.
  5. Iterate & Update: For each number in nums, iterate backwards through the DP array from KK down to that number’s value. This ensures we don’t use the same item multiple times for a single subset calculation (standard knapsack optimization).
    • Formula: dp[j] += dp[j - num]
  6. Result: Return dp[K].

Complexity Analysis

  • Time Complexity: O(N⋅K)O(N \cdot K), where NN is the length of nums and K=(total_sum+S)/2K = (total\_sum + S) / 2. Given constraints (Σ≤1000\Sigma \le 1000, SS bounded by logic), this effectively runs in roughly O(20×1000)O(20 \times 1000), which is negligible.
  • Space Complexity: O(K)O(K) for the DP array. Since Σ≤1000\Sigma \le 1000, space usage is minimal (approx 4KB).

Solution

from typing import List

def findTargetSumWays(nums: List[int], S: int) -> int:
    total_sum = sum(nums)
    
    # Check if target is reachable based on parity and bounds.
    # We need P - M = S, where P + M = total_sum. 
    # This implies 2*P = total_sum + S.
    # If (total_sum + S) < 0 or odd, it's impossible to form integer subset sum P >= 0
    
    if abs(S) > total_sum:
        return 0
        
    target_subset_sum = (total_sum + S) // 2
    
    # Parity check for valid non-negative solution. 
    # If the required subset sum is not an exact half-integer, no integer partition exists.
    if (target_subset_sum < 0): 
        return 0

    dp = [0] * (target_subset_sum + 1)
    dp[0] = 1
    
    for num in nums:
        # Iterate backwards to avoid using the same item multiple times per subset sum level
        for j in range(target_subset_sum, num - 1, -1):
            dp[j] += dp[j - num]
            
    return dp[target_subset_sum]

Edge Cases Handled

  • Impossible Target: If abs(S) is greater than the total sum of elements, we immediately return 0. This handles cases where S requires more positive value than available numbers can provide.
  • Parity Mismatch: The math derivation 2P=total+S2P = \text{total} + S implies that (total+S)(\text{total} + S) must be even for a valid integer subset sum to exist. If odd, the code returns 0 (handled by logic before array creation).
  • Negative Target: The problem allows S to be negative. Our math transformation handles this naturally; if SS is very negative such that (total+S)<0(\text{total} + S) < 0, we return 0, which is correct because subset sums of non-negative integers cannot be negative (in the context of P being a sum of positive numbers).
  • Empty Array: While constraints say length ≥1\ge 1, the logic sum(nums) handles empty lists gracefully (returns sum=0), though strictly not required by prompt.