LeetCode 494 - Target Sum

LeetCode Problem 494

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Backtracking

Solution

Problem Understanding

The problem asks us to count how many different ways we can assign either a '+' or '-' sign to every number in the array nums such that the resulting arithmetic expression evaluates to target.

Each number must be used exactly once, and for every position we have only two choices:

• Add the number
• Subtract the number

For example, if nums = [1, 2], the possible expressions are:

• +1 +2 = 3
• +1 -2 = -1
• -1 +2 = 1
• -1 -2 = -3

The goal is not to return the expressions themselves, but instead the total count of valid expressions whose final sum equals target.

The input consists of:

• nums, an integer array
• target, the desired final sum

The output is a single integer representing the number of valid sign assignments.

The constraints are extremely important for choosing the right algorithm:

• nums.length <= 20
• sum(nums) <= 1000

A length of 20 means brute force is technically possible because 2^20 is about one million combinations. However, while that may pass in some languages with optimizations, it is still exponential and not ideal for interview-quality dynamic programming problems.

The small total sum, capped at 1000, is the real clue. Problems involving combinations of sums with relatively small total ranges often suggest dynamic programming based on subset sums.

Several edge cases are important:

• Arrays containing zeros, because +0 and -0 are different choices and both count separately.
• Targets larger than the total possible sum, because such cases are impossible immediately.
• Negative targets, since the target can range from -1000 to 1000.
• Arrays with only one element.
• Cases where no valid expression exists.

Understanding how sign assignment affects the total sum is the key insight that leads to the optimal solution.

Approaches

Brute Force Approach

The most direct solution is to try every possible assignment of '+' and '-'.

For each number, we make one of two choices:

• Add it to the current total
• Subtract it from the current total

This naturally forms a binary decision tree. Since there are n numbers and each has two choices, there are 2^n total expressions.

A recursive backtracking solution explores every path:

• Start at index 0 with current sum 0
• Recursively try adding the current number
• Recursively try subtracting the current number
• When all numbers are processed, check whether the final sum equals target

This approach is correct because it exhaustively enumerates every possible expression.

However, it becomes inefficient because many subproblems repeat. For example, different paths may reach the same index with the same running sum, causing redundant computation.

Optimal Dynamic Programming Approach

The key insight comes from rewriting the mathematical relationship.

Suppose:

• P is the sum of numbers assigned '+'
• N is the sum of numbers assigned '-'

Then:

$$P - N = target$$

Also:

$$P + N = totalSum$$

Adding the equations gives:

$$2P = target + totalSum$$

So:

$$P = \frac{target + totalSum}{2}$$

This transforms the problem into:

Count the number of subsets whose sum equals (target + totalSum) / 2.

This is now a classic subset sum counting problem.

The transformation only works if:

• target + totalSum is even
• abs(target) <= totalSum

Otherwise, the answer is immediately 0.

We then use dynamic programming where:

• dp[s] stores the number of ways to form sum s

For each number, we update the DP array in reverse order to avoid reusing the same number multiple times.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Tries every possible sign assignment recursively
Optimal	O(n × S)	O(S)	Converts problem into subset sum counting, where S is transformed target

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

1. Compute the total sum of all numbers.

totalSum = sum(nums)

This value determines the maximum possible magnitude any expression can reach. 2. Check whether a valid transformation is possible.

The subset-sum transformation requires:

$$P = \frac{target + totalSum}{2}$$

If target + totalSum is odd, then P is not an integer, so no solution exists.

If abs(target) > totalSum, then even assigning all signs positively or negatively cannot reach the target. 3. Compute the subset sum target.

subsetTarget = (target + totalSum) // 2

The problem is now reduced to counting subsets whose sum equals subsetTarget. 4. Initialize the dynamic programming array.

Create an array:

dp[i] = number of ways to form sum i

Initially:

dp[0] = 1

There is exactly one way to form sum 0, choose no elements. 5. Process each number in nums.

For every number, update the DP array backward.

Backward traversal is important because each number can only be used once. 6. Update subset counts.

For every valid sum:

dp[currentSum] += dp[currentSum - num]

This means:

• Existing ways remain
• New ways are created by including the current number

7. Return the final answer.

After processing all numbers:

dp[subsetTarget]

contains the total number of valid expressions.

Why it works

The algorithm works because every valid sign assignment corresponds uniquely to a partition of the numbers into two groups:

• Positive numbers
• Negative numbers

By algebraically transforming the equation, we reduce the problem to counting subsets with a specific sum. The dynamic programming table correctly counts all possible subsets because each state accumulates the number of ways to reach a given sum using previously processed numbers.

Python Solution

from typing import List

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)

        # Impossible cases
        if abs(target) > total_sum:
            return 0

        if (target + total_sum) % 2 != 0:
            return 0

        subset_target = (target + total_sum) // 2

        # dp[i] = number of ways to form sum i
        dp = [0] * (subset_target + 1)
        dp[0] = 1

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

        return dp[subset_target]

The implementation begins by calculating the total sum of the array. This allows us to quickly reject impossible cases.

The first rejection condition checks whether the target magnitude exceeds the total possible sum. If the target is larger than all numbers combined, no sign assignment can reach it.

The second rejection condition checks parity. Since the transformed subset equation requires division by two, the result must be an integer.

Next, the algorithm computes subset_target, which represents the subset sum we need to count.

The dynamic programming array is then initialized. dp[0] = 1 represents the empty subset.

For each number, the algorithm iterates backward through the DP array. Backward iteration ensures each number is used only once per subset construction.

Each update:

dp[current_sum] += dp[current_sum - num]

means:

• The existing ways to form current_sum remain valid
• Additional ways are created by including num

Finally, dp[subset_target] contains the total number of valid expressions.

Go Solution

func findTargetSumWays(nums []int, target int) int {
	totalSum := 0
	for _, num := range nums {
		totalSum += num
	}

	// Impossible cases
	if abs(target) > totalSum {
		return 0
	}

	if (target+totalSum)%2 != 0 {
		return 0
	}

	subsetTarget := (target + totalSum) / 2

	dp := make([]int, subsetTarget+1)
	dp[0] = 1

	for _, num := range nums {
		for currentSum := subsetTarget; currentSum >= num; currentSum-- {
			dp[currentSum] += dp[currentSum-num]
		}
	}

	return dp[subsetTarget]
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

The Go implementation follows the same logic as the Python version.

The primary difference is manual handling of helper functionality such as abs, since Go does not provide a built-in integer absolute value function in the standard library.

Slices are used for the DP array. Since Go arrays are fixed size, slices provide the flexibility needed for dynamic programming.

Integer overflow is not a concern because the constraints are small. The maximum number of combinations is bounded by 2^20, which safely fits within Go's integer range.

Worked Examples

Example 1

Input:

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

First compute:

totalSum = 5

Transformation:

$$subsetTarget = \frac{3 + 5}{2} = 4$$

Now count subsets with sum 4.

Initial DP:

Sum	0	1	2	3	4
Ways	1	0	0	0	0

After first 1:

Sum	0	1	2	3	4
Ways	1	1	0	0	0

After second 1:

Sum	0	1	2	3	4
Ways	1	2	1	0	0

After third 1:

Sum	0	1	2	3	4
Ways	1	3	3	1	0

After fourth 1:

Sum	0	1	2	3	4
Ways	1	4	6	4	1

After fifth 1:

Sum	0	1	2	3	4
Ways	1	5	10	10	5

Final answer:

dp[4] = 5

Example 2

Input:

nums = [1]
target = 1

Compute:

totalSum = 1
subsetTarget = (1 + 1) / 2 = 1

Initial DP:

Sum	0	1
Ways	1	0

Process 1:

Sum	0	1
Ways	1	1

Final answer:

dp[1] = 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × S)	n numbers and subset sums up to S
Space	O(S)	One-dimensional DP array of size S + 1

Here, S is the transformed subset target:

$$S = \frac{target + totalSum}{2}$$

Since totalSum <= 1000, the DP array remains small and efficient.

The algorithm processes each number once and updates all reachable sums up to S, giving time complexity O(n × S).

The optimized one-dimensional DP array reduces space usage from O(n × S) to O(S).

Test Cases

sol = Solution()

assert sol.findTargetSumWays([1,1,1,1,1], 3) == 5
# Standard example with multiple solutions

assert sol.findTargetSumWays([1], 1) == 1
# Single element exact match

assert sol.findTargetSumWays([1], -1) == 1
# Single element negative target

assert sol.findTargetSumWays([1], 2) == 0
# Impossible target larger than total sum

assert sol.findTargetSumWays([0,0,0,0,0], 0) == 32
# Every zero doubles the number of valid expressions

assert sol.findTargetSumWays([2,3,5,7], 17) == 1
# All numbers must be positive

assert sol.findTargetSumWays([2,3,5,7], -17) == 1
# All numbers must be negative

assert sol.findTargetSumWays([1,2,3], 0) == 2
# Multiple balanced expressions

assert sol.findTargetSumWays([1000], -1000) == 1
# Largest single value negative

assert sol.findTargetSumWays([1000], 1000) == 1
# Largest single value positive

assert sol.findTargetSumWays([1,2,7,9,981], 1000000000) == 0
# Extremely impossible target

assert sol.findTargetSumWays([0,1], 1) == 2
# Zero creates duplicate valid expressions

Test	Why
[1,1,1,1,1], 3	Standard example with multiple combinations
[1], 1	Smallest positive valid case
[1], -1	Negative target handling
[1], 2	Impossible target detection
[0,0,0,0,0], 0	Verifies zero duplication behavior
[2,3,5,7], 17	All positive signs required
[2,3,5,7], -17	All negative signs required
[1,2,3], 0	Balanced partition scenario
[1000], -1000	Maximum negative boundary
[1000], 1000	Maximum positive boundary
[1,2,7,9,981], 1000000000	Extremely impossible target
[0,1], 1	Zero affecting combination count

Edge Cases

Arrays Containing Zeroes

Zeroes are particularly tricky because +0 and -0 produce the same numeric value but represent different expressions.

For example:

nums = [0,0]
target = 0

There are four valid expressions:

+0 +0
+0 -0
-0 +0
-0 -0

A naive implementation might accidentally collapse these into one result. The dynamic programming solution handles this naturally because each zero doubles the count of every reachable sum.

Impossible Targets

If the absolute value of the target exceeds the total sum of all numbers, the answer must be zero.

Example:

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

Even assigning all numbers positively only produces 6, so reaching 10 is impossible.

The implementation detects this immediately:

if abs(target) > total_sum:
    return 0

This prevents unnecessary DP computation.

Odd Transformation Results

The subset sum transformation requires:

$$subsetTarget = \frac{target + totalSum}{2}$$

If target + totalSum is odd, the subset target is not an integer, meaning no valid partition exists.

Example:

nums = [1,2]
target = 2

Then:

$$(2 + 3) / 2 = 2.5$$

Since subset sums must be integers, the answer is automatically zero.

The implementation handles this safely with:

if (target + total_sum) % 2 != 0:
    return 0

This is one of the most common bugs in incorrect solutions.