Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 494. Target Sum

Count how many ways to assign +/− to each element of nums so the signed sum equals target. This reduces to a subset-sum problem: count subsets with sum (sum(nums)+target)/2 (must be integral and nonnegative), typically solved with DP — watch parity and zeros.

Asked at:

DESCRIPTION

Input:

nums = [1, 1, 1, 1, 1], target = 3

Output:

Explanation: There are 5 ways to assign signs: +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. Each corresponds to choosing 4 elements for the positive subset (sum = 4) and 1 for negative (sum = 1), giving 4-1 = 3.

Constraints:

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
(sum(nums) + target) must be even and non-negative for a solution to exist

Understanding the Problem

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?

Brute Force Approach

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.

Visualization

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

Start backtracking to find all ways to assign +/- to reach target

0 / 198

Test Your Knowledge

Complexity Analysis

Time Complexity: O(2^n) We explore 2 choices (+ or -) for each of n elements, resulting in 2^n total combinations to check

Space Complexity: O(n) The recursion stack depth is at most n (one level per element in the array)

Building Intuition

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.

Common Mistakes

Forgetting to check if (sum + target) is even before attempting to solve - if it's odd, there's no valid partition and the answer is 0

Not handling the case where target > sum(nums) or target < -sum(nums) - these are impossible to achieve and should return 0

Iterating forward instead of backward when updating the DP array - forward iteration causes elements to be used multiple times in the same iteration

Not initializing dp[0] = 1 - this base case represents the one way to achieve sum 0 (by selecting no elements) and is crucial for the DP recurrence to work

Forgetting that the problem asks for COUNT of ways, not just whether a solution exists - the DP must accumulate counts, not just track boolean feasibility

Optimal Solution

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].

Visualization

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]

Start target sum algorithm

0 / 51

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n * P) We iterate through n elements, and for each element we update the dp array up to sum P, where P = (sum(nums) + target) / 2. This gives O(n * P) time complexity.

Space Complexity: O(P) We use a 1D dp array of size P+1 to store the count of ways to achieve each sum from 0 to P

What We've Learned

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.

Test Your Understanding

Why is array the right data structure for this problem?

array provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early November, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 494. Target Sum

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact