Plain-English Restatement: You have a list of numbers. For every number, you must choose to either add it or subtract it. Your goal is to find how many different ways you can assign these plus and minus signs so that the final evaluated math expression equals a specific target number.
Brute Force Approach: As mentioned in the pattern, the brute force approach is to try every possible combination of signs. We can write a recursive function that at index i branches into two paths: one adding nums[i] to our running total, and one subtracting it.
Time Complexity:O(2^n). There are 2 choices for each of the n numbers. For n=20, 2^{20} \approx 1,000,000, which actually passes on LeetCode but is slow. For n=40, it would immediately time out.
Why it's wasteful: If we have [1, 1, 1, 1...], doing +1 -1 and -1 +1 both result in a running sum of 0 at index 2. The brute force approach calculates the remaining 18 numbers identically for both branches. DP/Memoization merges these identical states.
The brute force tries 2^n sign assignments. With n = 20 that is a million, which actually passes — but the intended solution is much better and comes from a short piece of algebra.
Split the numbers into two groups:P gets a plus, N gets a minus. Then:
class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: total = sum(nums) if abs(target) > total or (target + total) % 2: return 0 # impossible subset_target = (target + total) # (1) 2 dp = [0] * (subset_target + 1) # (2) dp[0] = 1 # (3) one way to make 0: choose nothing for n in nums: # (4) for t in range(subset_target, n - 1, -1): # (5) DOWNWARDS: each once dp[t] += dp[t - n] # (6) return dp[subset_target]
ts
function findTargetSumWays(nums: number[], target: number): number { const total = nums.reduce((a, b) => a + b, 0); if (Math.abs(target) > total || (target + total) % 2 !== 0) return 0; const subsetTarget = (target + total) / 2; // (1) const dp = new Array(subsetTarget + 1).fill(0); // (2) dp[0] = 1; // (3) for (const n of nums) { // (4) for (let t = subsetTarget; t >= n; t--) { // (5) dp[t] += dp[t - n]; // (6) } } return dp[subsetTarget];}
(2) Setup DP.dp = [0] * (subset_target + 1). dp[t] will hold the number of ways to pick a subset of numbers that sum to exactly t.
(3) Base Case.dp[0] = 1. There's exactly 1 way to get a sum of 0: pick none of the numbers.
(4) Outer Loop.for n in nums:. We consider each number one by one.
(5) Inner Loop (Downwards).for t in range(subset_target, n - 1, -1):. We iterate backwards from the target down to n. We stop at n because we can't possibly use n to make a sum smaller than n.
(6) The Transition.dp[t] += dp[t - n]. We update the number of ways to make sum t by adding the number of ways we could make t - n. Because we iterate backwards, dp[t - n] still contains the value from the previous step (before we considered the current n). This guarantees we use n at most once.
The inner loop counts downwards, because each number gets exactly one sign — it is used once. Counting upwards would let a number be used repeatedly, which is the unbounded knapsack and a different problem. That is the direction rule from 4.22 and 4.24.4.
dp[0] = 1 — one way to make zero, by choosing nothing. Every count is built from it.
Zeros in the input work correctly, and they are worth checking. A zero can carry either sign, so it doubles the number of assignments. In this code, processing a 0 runs dp[t] += dp[t - 0], which doubles every entry — exactly right, and it happens with no special case.
If the algebra does not arrive, there is a solution that works straight from the problem: track how many ways reach each running sum.
python
from collections import defaultdictdef findTargetSumWays(self, nums, target): ways = {0: 1} for n in nums: nxt = defaultdict(int) for s, count in ways.items(): nxt[s + n] += count nxt[s - n] += count ways = nxt return ways.get(target, 0)
The number of distinct running sums is bounded by 2 × total + 1, so this is O(n \times \text{total}) — the same complexity, using a dictionary because sums can be negative.
Say this one if the reduction does not come to you. A correct solution of the right complexity beats a stalled attempt at the elegant one.
Time Complexity:O(n \times \text{total}). The subset target is bounded by total. We have an outer loop of size n, and an inner loop of size at most total.
Space Complexity:O(\text{total}). We use a 1D array of size subset_target + 1, which scales linearly with the sum of the array elements.
Target is impossible to reach (too large): If abs(target) > total, we catch it early and return 0.
Target is impossible to reach (parity mismatch): If (target + total) is odd, we catch it early and return 0.
Zeroes in input: As noted, if n = 0, the inner loop will execute for all valid t, updating dp[t] += dp[t - 0], effectively doubling the count (since a 0 can be either +0 or -0).
Partition Equal Subset Sum — the same knapsack asking whether rather than how many. 4.23.12.
Last Stone Weight II — minimise the difference between two groups, which is subset sum nearest total / 2.
Ones and Zeroes — a knapsack with two capacities, so the table gains a dimension.
A habit to build: before writing any DP, spend thirty seconds asking whether the problem can be rewritten into one you already know. The algebra here turned a sign-assignment problem into a subset count. That reduction teaches more than any detail of the code.
"Derive the reduction." Two equations, add them, the negative group cancels. Do it on the board — it is short and it is the answer they want.
"What are the impossibility checks?" Odd parity, and a target larger than the total.
"Why does the inner loop go down?" Each number gets one sign, so it is used once.
"What do zeros do?" They double the count, and the code handles it with no special case.
"What if you could not find the reduction?" The running-sums dictionary, same complexity.
One thing to volunteer: point out the zero case before being asked. It is the input most likely to break a solution that special-cases things, and noticing that the plain code already handles it shows you traced it.