Difficulty: Medium2-D Dynamic Programming

Target Sum

Problem in Plain English

Given an array of numbers and a target, count how many ways a plus or minus sign can be placed before each number so the resulting expression equals the target.

Problem Statement

You are given an integer array nums and an integer target. Place either + or - before every element of nums, then evaluate the expression. Return the number of different sign assignments that evaluate to target.

For nums = [1, 1, 1, 1, 1] and target = 3, the answer is 5: the five expressions with four plus signs and one minus sign each total $5 - 2 = 3$ .

Constraints

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums) <= 1000
-1000 <= target <= 1000

Examples

Example 1

Input: nums = [1, 1, 1, 1, 1], target = 3
Output: 5

Exactly one position must carry a minus: -++++, +-+++, ++-++, +++-+, and ++++-. Each expression sums to 3; the five equal values still occupy five distinct positions.

Example 2

Input: nums = [1], target = 1
Output: 1

There are two complete assignments, +1 and -1. Only +1 equals 1, so count one.

Example 3

Input: nums = [0, 0, 1], target = 1
Output: 4

The final 1 must have a plus. Each zero independently takes either sign: +0+0+1, +0-0+1, -0+0+1, and -0-0+1 are four distinct expressions with the same value.

Example 4

Input: nums = [1, 2], target = 0
Output: 0

The four expressions evaluate to 3, -1, 1, and -3. None equals zero. Equivalently, S + target = 3 is odd, so no integer plus-subset sum exists.

Example 5

Input: nums = [1, 2], target = -1
Output: 1

Only +1-2 reaches -1. Here S = 3 and the plus-group goal is (3 - 1) / 2 = 1, represented by the first position alone.

Intuition

A sign belongs to an array position, so equal numbers and the two signs on zero remain separate choices. In Example 1 the five ones total 5; negating any one position reduces the total by twice that value, giving 3. A recursive search counts every complete choice. To avoid repeating work, group positions carrying a plus sign into a subset: if its sum is P and all numbers sum to S, then P - (S - P) = target. Thus we can count subsets of positions totaling (S + target) / 2 instead of constructing every expression.

Approaches

Brute Force Recursion

Solution Details

Reveal Brute Force Recursion: intuition, complexity, and code

Intuition

Choose a sign for the next position, recursively finish the remaining positions, and add the counts returned by the two branches. A running total is not a success until every number has a sign. Equal running totals may recur, but this baseline deliberately recomputes them to expose the exponential cost.

Step-by-Step Logic

Start dfs(0, 0) for Example 1; index records how many of the five positions have received signs.
At each nonterminal state call the plus child first, then the minus child, and add their returned counts. The first two levels go from (0, 0) to (1, 1)/(1, -1), then totals 2, 0, 0, and -2.
Continue until index 5. The all-plus path reaches total 5 and returns 0; the path ++++- reaches total 3 and returns 1. Reaching total 3 at index 3 is not enough because two signs remain.
Unwind by addition: dfs(4, 4) returns 0 + 1 = 1; dfs(4, 2) returns 1 + 0 = 1; dfs(3, 3) therefore returns 2.
The root plus branch returns 4 and the root minus branch returns 1, so return 5. The trace groups identical states for readability; the code does not cache them and performs all 63 calls, including all 32 leaves.

Why It Works

At state (index, total), total is the signed sum of exactly the positions before index. Giving the next position a plus or a minus partitions all remaining assignments into two disjoint sets, even if the value is zero and both child totals coincide. At index n, no choices remain, so return one precisely when total equals target and zero otherwise. Adding the two child counts therefore counts each full sign vector once, and the root (0, 0) counts all valid expressions.

Dry Run

Brute Force Recursion: variable states at each step
State (index, total)	Times called	Plus child and return	Minus child and return	Return per call
(0, 0)	1	(1, 1) -> 4	(1, -1) -> 1	5; final answer
(1, 1)	1	(2, 2) -> 3	(2, 0) -> 1	4
(1, -1)	1	(2, 0) -> 1	(2, -2) -> 0	1
(2, 2)	1	(3, 3) -> 2	(3, 1) -> 1	3
(2, 0)	2	(3, 1) -> 1	(3, -1) -> 0	1
(2, -2)	1	(3, -1) -> 0	(3, -3) -> 0	0
(3, 3)	1	(4, 4) -> 1	(4, 2) -> 1	2
(3, 1)	3	(4, 2) -> 1	(4, 0) -> 0	1
(3, -1)	3	(4, 0) -> 0	(4, -2) -> 0	0
(3, -3)	1	(4, -2) -> 0	(4, -4) -> 0	0
(4, 4)	1	(5, 5) -> 0	(5, 3) -> 1	1
(4, 2)	4	(5, 3) -> 1	(5, 1) -> 0	1
(4, 0)	6	(5, 1) -> 0	(5, -1) -> 0	0
(4, -2)	4	(5, -1) -> 0	(5, -3) -> 0	0
(4, -4)	1	(5, -3) -> 0	(5, -5) -> 0	0
(5, 5)	1	terminal	compare total with 3	0
(5, 3)	5	terminal	compare total with 3	1
(5, 1)	10	terminal	compare total with 3	0
(5, -1)	10	terminal	compare total with 3	0
(5, -3)	5	terminal	compare total with 3	0
(5, -5)	1	terminal	compare total with 3	0
root return	1	dfs(1, 1) = 4	dfs(1, -1) = 1	4 + 1 = 5

Complexity Analysis

Time Complexity

O(2^n)

Space Complexity

O(n)

Let n be nums.length. With no pruning or memoization, the complete binary recursion tree has 2^(n+1) - 1 calls and 2^n leaves; each call performs constant work. Only one root-to-leaf chain of n + 1 frames is live, and no input copies or expression strings are allocated. Depth is at most 21 frames. The count is at most 2^20 = 1048576, and signed totals stay within [-1000, 1000], so Java int and JavaScript Number are exact under these constraints. The input is not modified.

Code

Solution.java

1class Solution {2    public int findTargetSumWays(int[] nums, int target) {3        return dfs(nums, target, 0, 0);4    }5
6    private int dfs(int[] nums, int target, int index, int total) {7        if (index == nums.length) {8            return total == target ? 1 : 0;9        }10        // Count both sign choices separately, including +0 and -0.11        return dfs(nums, target, index + 1, total + nums[index])12                + dfs(nums, target, index + 1, total - nums[index]);13    }14}

Hints

Hint 1

Describe a recursive state by the next index and the signed total so far. Count a match only after every position has a sign.

Hint 2

Let the plus group sum to P and all values sum to S. What does P - (S - P) = target force P to be?

Hint 3

Reject an out-of-range target or odd S + target. Count subsets of positions reaching the integer goal, retaining multiplicity rather than a boolean.

Hint 4

To count each position at most once with one array, update sums backward. Include sum zero when the value is zero so both signs are counted.

Edge Cases

Zeros are independent positions: [0, 0, 1] with target 1 has four expressions. Twenty zeros with target 0 attain the maximum count, 1048576.
S = 0 and target = 0 still require processing every zero; the empty-subset initialization alone is not the final answer. A nonzero target is impossible.
A negative target is legal: [1, 2] with target -1 has one expression, +1-2. Sign reversal gives equal counts for target t and -t.
An odd S + target, such as [1, 2] with target 0, cannot produce an integer goal. Range is a necessary but insufficient condition.
Targets outside [-S, S] return zero. Targets equal to S or -S require all nonzero values to share the corresponding sign, while each zero still doubles the count.
Repeated values stay distinct by index: the five equal ones in Example 1 yield five choices for the minus position.

Common Mistakes and Interview Tips

Returning success as soon as a running total reaches target skips the signs still required on the remaining numbers. Test equality only at the terminal recursion state.
Deduplicating equal numbers or merging +0 and -0 counts values rather than expressions and loses valid assignments.
Updating positive subset sums upward reuses the same position within one pass, turning 0/1 counting into unlimited reuse.
Stopping the DP loop at s > 0 misses the zero-value update to dp[0]; with all zeros this returns one instead of 2^n.
Using boolean reachability answers whether an expression exists, not how many expressions exist. Add counts of disjoint choices.
Computing the goal before checking range and parity can allocate a negative-sized table or silently round an impossible half-integer.
Interview tip: justify the bijection between plus-position subsets and sign assignments, then demonstrate why a zero doubles the table and why a positive value requires a backward scan.

Key Takeaway

A binary sign choice can become subset counting when the two groups partition a fixed total. Derive the forced sum, reject impossible parity and range, and use a backward 0/1 count so positions, duplicates, and zeros retain their multiplicity.