5
total
Assign + or - to each number to hit a target. The trick is seeing that this is a subset-sum count: the “positive subset” must sum to (total + target) / 2, turning an exponential DFS into an O(n × goal) 1-D DP.
Given an integer array nums and an integer target, assign a + or - sign to each number and return the count of expressions that evaluate to target.
Worked example: nums = [1, 1, 1, 1, 1], target = 3. There are 5 ways: -1+1+1+1+1, +1-1+1+1+1, +1+1-1+1+1, +1+1+1-1+1, +1+1+1+1-1. Answer: 5.
P be the subset assigned +. Then P − (total − P) = target, so P = (total + target) / 2. The number of ways to reach target equals the number of subsets that sum to this goal— a classic 0/1 knapsack count solvable in O(n × goal) with a 1-D DP array.(total + target) must be even (otherwise no integer split exists). Also bail if goal < 0.goal = (total + target) / 2. We need to count subsets of nums that sum to exactly goal.dp[j] = number of subsets summing to j. Set dp[0] = 1 (one way to reach 0: pick nothing).num iterate j from goal down to num: dp[j] += dp[j − num]. Reverse order prevents counting the same element twice.dp[goal] is the answer.j = goal … num). Going forwards would let the same num be picked multiple times, turning the 0/1 knapsack into an unbounded one and overcounting badly.Memoized DFS with state (index, remaining)also achieves O(n × total) time and is the natural alternative if you spot the recurrence before the algebraic reduction.
3. Compute total = 5.1▶function findTargetSumWays(nums: number[], target: number): number {2▶ const total = nums.reduce((a, b) => a + b, 0);34 // Assign + to a subset P and - to the rest.5 // P - (total - P) = target => P = (total + target) / 26 // So: count subsets of nums that sum to exactly goal.7 if ((total + target) % 2 !== 0) return 0; // no integer split8 const goal = (total + target) / 2;9 if (goal < 0) return 0;1011 // dp[j] = number of subsets summing to j12 const dp: number[] = new Array(goal + 1).fill(0);13 dp[0] = 1; // one way to make sum 0: pick nothing1415 for (const num of nums) {16 // iterate backwards to avoid using num twice17 for (let j = goal; j >= num; j--) {18 dp[j] += dp[j - num];19 }20 }2122 return dp[goal];23}
function findTargetSumWays(nums: number[], target: number): number {
const total = nums.reduce((a, b) => a + b, 0);
// Assign + to a subset P and - to the rest.
// P - (total - P) = target => P = (total + target) / 2
// So: count subsets of nums that sum to exactly goal.
if ((total + target) % 2 !== 0) return 0; // no integer split
const goal = (total + target) / 2;
if (goal < 0) return 0;
// dp[j] = number of subsets summing to j
const dp: number[] = new Array(goal + 1).fill(0);
dp[0] = 1; // one way to make sum 0: pick nothing
for (const num of nums) {
// iterate backwards to avoid using num twice
for (let j = goal; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[goal];
}(total + target) is odd there is no valid integer split, so return 0 immediately. Otherwise goal = (total + target) / 2— the exact sum the “positive” subset must reach. A negative goal also means zero ways.dp[j] counts subsets that sum to j. The empty subset sums to 0, so dp[0] = 1. Every other entry starts at 0 (no subsets yet considered).j downward from goal to num. The update dp[j] += dp[j − num]says: “add the count of all ways to reach j − num using previous numbers, because we can extend each of those ways by picking num.” The downward direction ensures each element is used at most once.dp[goal] holds the total number of subsets whose sum equals goal, which equals the number of sign assignments that reach target.goal = (sum(nums) + target) / 2. In the worst case goal ≤ sum(nums) ≤ 1000 (per constraints), so the DP is very fast in practice.goal formula still holds but goalcould exceed the array bounds — you'd need to memoize on (index, remaining_sum) instead.(index, remaining) and cache results in a Map. Same asymptotic complexity but potentially easier to derive in an interview before spotting the algebraic trick.target exceeds total (unreachable), when nums contains zeros (zeros double-count — but the DP handles them correctly since dp[j] += dp[j − 0] doubles existing ways), and when target = −total (all negatives, one way).function findTargetSumWays(nums: number[], target: number): number {
const total = nums.reduce((a, b) => a + b, 0);
// Assign + to a subset P and - to the rest.
// P - (total - P) = target => P = (total + target) / 2
// So: count subsets of nums that sum to exactly goal.
if ((total + target) % 2 !== 0) return 0; // no integer split
const goal = (total + target) / 2;
if (goal < 0) return 0;
// dp[j] = number of subsets summing to j
const dp: number[] = new Array(goal + 1).fill(0);
dp[0] = 1; // one way to make sum 0: pick nothing
for (const num of nums) {
// iterate backwards to avoid using num twice
for (let j = goal; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[goal];
}goal = (sum(nums) + target) / 2. In the worst case goal ≤ sum(nums) ≤ 1000 (per constraints), so the DP is very fast in practice.Try both a + and a - sign for each number, recursing to the end and counting every full assignment whose running sum equals target — the literal definition of the problem.
function findTargetSumWays(nums: number[], target: number): number {
const n = nums.length;
// dfs(i, sum) = number of ways to sign nums[i..] so the total hits target,
// given the prefix nums[0..i-1] already contributed sum.
const dfs = (i: number, sum: number): number => {
if (i === n) return sum === target ? 1 : 0;
// Branch: assign + to nums[i], then assign - to nums[i].
return dfs(i + 1, sum + nums[i]) + dfs(i + 1, sum - nums[i]);
};
return dfs(0, 0);
}(i, sum)collapses overlapping states to O(n × sum), and the algebraic subset-sum reduction removes the recursion entirely.| assign + or − to each element, count ways to reach target | subset-sum DP, goal = (total+target)/2 |
| count subsets summing to a fixed value | 1-D 0/1 knapsack, iterate j backwards |
| two complementary subsets (P and N) that differ by a fixed amount | sum algebra: P = (total+delta)/2 |
| DFS with (index, remaining) and overlapping sub-problems | memoized DFS or flatten to DP |
function findTargetSumWays(nums: number[], target: number): number {
const total = nums.reduce((a, b) => a + b, 0);
if ((total + target) % 2 !== 0) return 0;
const goal = (total + target) / 2;
if (goal < 0) return 0;
const dp = new Array(goal + 1).fill(0);
dp[0] = 1;
for (const num of nums) {
for (let j = goal; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[goal];
}P − (total − P) = target ⇒ P = (total + target) / 2. Count subsets summing to P.nums = [1,1,1,1,1], target = 3, what is goal = (total + target) / 2?findTargetSumWays immediately return 0?dp[0] is initialized to 1. What does that represent?nums = [1, 1, 1, 1, 1], target = 3, what does the algorithm return?