Target Sum
Description
You are given an integer array nums and an integer target.
Your goal is to build a mathematical expression by placing either a '+' or '-' sign in front of every element in nums, then evaluating the resulting expression.
For example, if nums = [2, 1], you could form "+2-1" = 1 or "-2+1" = -1.
Return the number of different sign assignments that make the expression evaluate to exactly target.
Examples
Example 1
Input: nums = [1, 1, 1, 1, 1], target = 3
Output: 5
Explanation: There are 5 ways to assign signs such that the expression equals 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
- +1 + 1 + 1 + 1 − 1 = 3
In each valid assignment, exactly one element receives a minus sign, and the remaining four receive plus signs. There are C(5,1) = 5 such choices.
Example 2
Input: nums = [1], target = 1
Output: 1
Explanation: The only valid assignment is +1 = 1. Assigning a minus gives −1, which does not equal 1.
Example 3
Input: nums = [2, 2, 2], target = 2
Output: 3
Explanation: Three valid assignments:
- +2 + 2 − 2 = 2
- +2 − 2 + 2 = 2
- −2 + 2 + 2 = 2
Constraints
- 1 ≤ nums.length ≤ 20
- 0 ≤ nums[i] ≤ 1000
- 0 ≤ sum(nums[i]) ≤ 1000
- -1000 ≤ target ≤ 1000
Editorial
Brute Force
Intuition
The most straightforward approach is to try every possible combination of signs. For each element in the array, we have exactly two choices: assign a + (add it) or assign a − (subtract it). This gives us 2^n total combinations.
We can explore all combinations using recursion. Starting from the first element, we branch into two paths — one where we add the current element to a running sum and one where we subtract it. When we reach the end of the array, we check whether the running sum equals the target. If it does, we count that path.
Think of it as a binary decision tree: at each level, you flip a coin — heads means add, tails means subtract. Count the number of coin-flip sequences that land on the target sum.
Step-by-Step Explanation
Let's trace through with nums = [1, 1, 1, 1, 1], target = 3:
Step 1: Start at index 0, currentSum = 0. For each element, choose + or −.
Step 2: Element 0: choose +1 → sum = 1. Continue down this path.
Step 3: Element 1: choose +1 → sum = 2. Element 2: choose +1 → sum = 3. We've matched the target with 2 elements remaining.
Step 4: Element 3: choose +1 → sum = 4. Element 4: must choose −1 to get 4 − 1 = 3. ✓ Path: +1+1+1+1−1 = 3.
Step 5: Back to element 3: choose −1 → sum = 2. Element 4: choose +1 → 2 + 1 = 3. ✓ Path: +1+1+1−1+1 = 3.
Step 6: Back to element 2: choose −1 → sum = 1. Then +1+1 → sum = 3. ✓ Path: +1+1−1+1+1 = 3.
Step 7: Back to element 1: choose −1 → sum = 0. Then +1+1+1 → sum = 3. ✓ Path: +1−1+1+1+1 = 3.
Step 8: Back to element 0: choose −1 → sum = −1. Then +1+1+1+1 → sum = 3. ✓ Path: −1+1+1+1+1 = 3.
Step 9: All 2^5 = 32 leaf nodes explored. 5 paths yield sum = 3. Return 5.
Exploring All Sign Assignments Recursively — Watch how the recursion branches at each element (+ or −), building a binary tree of all possible expressions. We count leaves where the sum equals the target.
Algorithm
- Define solve(index, currentSum):
- If index == n: return 1 if currentSum == target, else 0.
- Add nums[index]: count1 = solve(index + 1, currentSum + nums[index])
- Subtract nums[index]: count2 = solve(index + 1, currentSum − nums[index])
- Return count1 + count2
- Call solve(0, 0) and return the result.
Code
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
return solve(nums, 0, 0, target);
}
private:
int solve(vector<int>& nums, int index, int currentSum, int target) {
if (index == nums.size()) {
return currentSum == target ? 1 : 0;
}
int add = solve(nums, index + 1, currentSum + nums[index], target);
int sub = solve(nums, index + 1, currentSum - nums[index], target);
return add + sub;
}
};class Solution:
def findTargetSumWays(self, nums: list[int], target: int) -> int:
def solve(index, current_sum):
if index == len(nums):
return 1 if current_sum == target else 0
add = solve(index + 1, current_sum + nums[index])
sub = solve(index + 1, current_sum - nums[index])
return add + sub
return solve(0, 0)class Solution {
public int findTargetSumWays(int[] nums, int target) {
return solve(nums, 0, 0, target);
}
private int solve(int[] nums, int index, int currentSum, int target) {
if (index == nums.length) {
return currentSum == target ? 1 : 0;
}
int add = solve(nums, index + 1, currentSum + nums[index], target);
int sub = solve(nums, index + 1, currentSum - nums[index], target);
return add + sub;
}
}Complexity Analysis
Time Complexity: O(2^n)
Each element leads to two recursive calls (+ or −), forming a binary tree with 2^n leaf nodes. Every leaf is visited exactly once. For n = 20, this is about 10^6 — manageable but slow for larger inputs.
Space Complexity: O(n)
The recursion depth equals n (one level per element), so the call stack uses O(n) space.
Why This Approach Is Not Efficient
The brute force explores 2^n paths. With n = 20, that's ~10^6, which is borderline. But the real problem is overlapping subproblems: many different sign sequences lead to the same (index, currentSum) state.
For example, with nums = [1, 1, 1, ...], the path +1−1 and −1+1 both arrive at (index=2, sum=0). The brute force recomputes the entire subtree from that point for both paths.
The number of unique states is bounded by n × (2 × totalSum + 1), which for this problem is at most 20 × 2001 = ~40,000 — far fewer than 2^20 ≈ 10^6. Memoizing these states eliminates redundant work and leads directly to a DP solution.
Better Approach - 2D Dynamic Programming
Intuition
Instead of exploring the same subproblem repeatedly, we build a table that stores the number of ways to reach every possible sum using the first i elements.
Define dp[i][s] = number of ways to reach sum s using the first i elements of nums. Since sums can range from −totalSum to +totalSum, we use an offset so that sum s is stored at column index s + totalSum.
Base case: dp[0][0 + offset] = 1 — there is exactly one way to reach sum 0 using zero elements (do nothing).
Transition: When processing element nums[i-1], each existing sum s can either become s + nums[i-1] (add) or s − nums[i-1] (subtract):
- dp[i][j] += dp[i-1][j − nums[i-1]] (came from adding)
- dp[i][j] += dp[i-1][j + nums[i-1]] (came from subtracting)
The answer is dp[n][target + offset].
Step-by-Step Explanation
Let's trace through with nums = [1, 1, 1, 1, 1], target = 3. TotalSum = 5, offset = 5.
Step 1: Initialize: dp[0][5] = 1 (sum = 0, one way with zero elements). All other cells are 0.
Step 2: Process first 1. dp[1][4] = 1 (sum −1: subtract 1). dp[1][6] = 1 (sum +1: add 1).
Step 3: Process second 1. dp[2][5] = dp[1][4] + dp[1][6] = 1 + 1 = 2 (sum 0: two ways — +1−1 or −1+1). dp[2][3] = 1, dp[2][7] = 1.
Step 4: Process third 1. dp[3][8] = dp[2][7] + dp[2][9] = 1 + 0 = 1. First time sum +3 is reachable! dp[3][4] = 3, dp[3][6] = 3.
Step 5: Process fourth 1. dp[4][7] = 4, dp[4][5] = 6, dp[4][3] = 4, dp[4][9] = 1.
Step 6: Process fifth 1. dp[5][8] = dp[4][7] + dp[4][9] = 4 + 1 = 5.
Step 7: Target column = 3 + 5 = 8. dp[5][8] = 5 → return 5.
2D DP with Offset — Counting Sign Assignments — Watch how the number of ways to reach each sum accumulates row by row. Each cell is the sum of two cells from the row above (add or subtract the current element).
Algorithm
- Compute totalSum. If |target| > totalSum, return 0 (impossible).
- Set offset = totalSum, columns = 2 × totalSum + 1.
- Create dp table of size (n+1) × columns, initialized to 0.
- Set dp[0][offset] = 1 (sum 0 with 0 elements).
- For each element i from 1 to n:
- For each column j from 0 to columns−1:
- If j − nums[i-1] ≥ 0: dp[i][j] += dp[i-1][j − nums[i-1]] (add)
- If j + nums[i-1] < columns: dp[i][j] += dp[i-1][j + nums[i-1]] (subtract)
- For each column j from 0 to columns−1:
- Return dp[n][target + offset].
Code
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size();
int totalSum = 0;
for (int num : nums) totalSum += num;
if (abs(target) > totalSum) return 0;
int offset = totalSum;
int cols = 2 * totalSum + 1;
vector<vector<int>> dp(n + 1, vector<int>(cols, 0));
dp[0][offset] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < cols; j++) {
if (j - nums[i - 1] >= 0)
dp[i][j] += dp[i - 1][j - nums[i - 1]];
if (j + nums[i - 1] < cols)
dp[i][j] += dp[i - 1][j + nums[i - 1]];
}
}
return dp[n][target + offset];
}
};class Solution:
def findTargetSumWays(self, nums: list[int], target: int) -> int:
total_sum = sum(nums)
if abs(target) > total_sum:
return 0
offset = total_sum
cols = 2 * total_sum + 1
dp = [[0] * cols for _ in range(len(nums) + 1)]
dp[0][offset] = 1
for i in range(1, len(nums) + 1):
for j in range(cols):
if j - nums[i - 1] >= 0:
dp[i][j] += dp[i - 1][j - nums[i - 1]]
if j + nums[i - 1] < cols:
dp[i][j] += dp[i - 1][j + nums[i - 1]]
return dp[len(nums)][target + offset]class Solution {
public int findTargetSumWays(int[] nums, int target) {
int totalSum = 0;
for (int num : nums) totalSum += num;
if (Math.abs(target) > totalSum) return 0;
int offset = totalSum;
int cols = 2 * totalSum + 1;
int[][] dp = new int[nums.length + 1][cols];
dp[0][offset] = 1;
for (int i = 1; i <= nums.length; i++) {
for (int j = 0; j < cols; j++) {
if (j - nums[i - 1] >= 0)
dp[i][j] += dp[i - 1][j - nums[i - 1]];
if (j + nums[i - 1] < cols)
dp[i][j] += dp[i - 1][j + nums[i - 1]];
}
}
return dp[nums.length][target + offset];
}
}Complexity Analysis
Time Complexity: O(n × S) where S = 2 × totalSum + 1
We fill n rows, each with S columns. Each cell takes O(1) to compute. With n ≤ 20 and totalSum ≤ 1000, this is at most 20 × 2001 = 40,020 operations — very fast.
Space Complexity: O(n × S)
The 2D table stores (n+1) × S integers. In the worst case, this is 21 × 2001 ≈ 42,000 entries. While manageable, we can reduce this significantly by observing that we only need two rows at a time — or even better, by transforming the problem to avoid negative indices entirely.
Why This Approach Is Not Efficient
The 2D DP runs efficiently in terms of time, but the table includes many columns for sums that are unreachable — particularly extreme negative sums. The column range 2 × totalSum + 1 can be up to 2001, but only a fraction of those sums are ever reachable.
More importantly, there is a mathematical insight that transforms this problem into a simpler one. Let P be the sum of elements assigned '+' and N be the sum of elements assigned '−'. Then:
- P + N = totalSum (all elements contribute their absolute value)
- P − N = target (the expression must equal target)
Adding these equations: 2P = totalSum + target, so P = (totalSum + target) / 2.
This transforms the problem from "count sign assignments" into "count subsets that sum to P" — a classic 0/1 knapsack counting problem that can be solved with a compact 1D DP array of size P+1 instead of a wide 2D offset table.
Optimal Approach - Subset Sum Count (1D DP)
Intuition
Using the mathematical transformation P = (totalSum + target) / 2, the problem becomes: count the number of subsets of nums that sum to P.
If (totalSum + target) is odd or negative, no valid assignment exists — return 0 immediately.
We use a 1D DP array where dp[j] = number of subsets that sum to j. Start with dp[0] = 1 (one way to make sum 0: the empty subset). For each element, scan right to left and add dp[j - num] to dp[j] — this counts the new subsets that include the current element.
This is identical to the 0/1 knapsack counting variant. Scanning right to left ensures each element is used at most once per subset.
Step-by-Step Explanation
Let's trace through with nums = [1, 1, 1, 1, 1], target = 3.
Transform: P = (5 + 3) / 2 = 4. Count subsets summing to 4.
Step 1: Initialize dp = [1, 0, 0, 0, 0]. dp[0] = 1 means there is one way to make sum 0 (empty subset).
Step 2: Process nums[0] = 1. j = 1: dp[1] += dp[0] = 0 + 1 = 1. dp = [1, 1, 0, 0, 0].
Step 3: Process nums[1] = 1. j = 2: dp[2] += dp[1] = 0 + 1 = 1. j = 1: dp[1] += dp[0] = 1 + 1 = 2. dp = [1, 2, 1, 0, 0].
Step 4: Process nums[2] = 1. j = 3: dp[3] += dp[2] = 0 + 1 = 1. j = 2: dp[2] += dp[1] = 1 + 2 = 3. j = 1: dp[1] += dp[0] = 2 + 1 = 3. dp = [1, 3, 3, 1, 0].
Step 5: Process nums[3] = 1. j = 4: dp[4] += dp[3] = 0 + 1 = 1. j = 3: dp[3] += dp[2] = 1 + 3 = 4. j = 2: dp[2] += dp[1] = 3 + 3 = 6. j = 1: dp[1] += dp[0] = 3 + 1 = 4. dp = [1, 4, 6, 4, 1].
Step 6: Process nums[4] = 1. j = 4: dp[4] += dp[3] = 1 + 4 = 5! j = 3: dp[3] = 10. j = 2: dp[2] = 10. j = 1: dp[1] = 5. dp = [1, 5, 10, 10, 5].
Result: dp[4] = 5 → return 5.
1D Subset Sum Count — Right-to-Left Sweep — Watch the dp array evolve as each element is processed. Each cell dp[j] counts subsets summing to j. Right-to-left scanning ensures each element is used at most once.
Algorithm
- Compute totalSum. Check feasibility:
- If |target| > totalSum or (totalSum + target) is odd or negative: return 0.
- Compute P = (totalSum + target) / 2.
- Create dp array of size P+1, initialized to 0. Set dp[0] = 1.
- For each num in nums:
- For j from P down to num:
- dp[j] += dp[j - num]
- For j from P down to num:
- Return dp[P].
Code
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int totalSum = 0;
for (int num : nums) totalSum += num;
// Feasibility checks
if (abs(target) > totalSum) return 0;
if ((totalSum + target) % 2 != 0) return 0;
if (totalSum + target < 0) return 0;
int subsetTarget = (totalSum + target) / 2;
vector<int> dp(subsetTarget + 1, 0);
dp[0] = 1;
for (int num : nums) {
for (int j = subsetTarget; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[subsetTarget];
}
};class Solution:
def findTargetSumWays(self, nums: list[int], target: int) -> int:
total_sum = sum(nums)
# Feasibility checks
if abs(target) > total_sum:
return 0
if (total_sum + target) % 2 != 0:
return 0
if total_sum + target < 0:
return 0
subset_target = (total_sum + target) // 2
dp = [0] * (subset_target + 1)
dp[0] = 1
for num in nums:
for j in range(subset_target, num - 1, -1):
dp[j] += dp[j - num]
return dp[subset_target]class Solution {
public int findTargetSumWays(int[] nums, int target) {
int totalSum = 0;
for (int num : nums) totalSum += num;
// Feasibility checks
if (Math.abs(target) > totalSum) return 0;
if ((totalSum + target) % 2 != 0) return 0;
if (totalSum + target < 0) return 0;
int subsetTarget = (totalSum + target) / 2;
int[] dp = new int[subsetTarget + 1];
dp[0] = 1;
for (int num : nums) {
for (int j = subsetTarget; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[subsetTarget];
}
}Complexity Analysis
Time Complexity: O(n × P) where P = (totalSum + target) / 2
For each of the n elements, we iterate through at most P values in the inner loop. P ≤ totalSum ≤ 1000, and n ≤ 20, so at most 20,000 operations. This is significantly better than O(n × 2S) of the offset-based 2D DP when the target is small relative to totalSum.
Space Complexity: O(P)
We use a single 1D array of size P + 1. Since P ≤ 1000, this is at most 1001 integers — a dramatic reduction from the 2D table's O(n × 2 × totalSum) space. This is the optimal space complexity because we need at least O(P) space to track which subset sums are reachable.