Put a '+' or '−' in front of every number in nums and evaluate the expression. Return how many different sign assignments evaluate to target.
Call P the numbers given '+'. Then P − (total − P) = target, so P = (total + target) / 2. Count subsets with that sum using a 1D knapsack, iterating sums downward.
1function findTargetSumWays(nums: number[], target: number): number {2const total = nums.reduce((a, b) => a + b, 0);3if ((total + target) % 2 || Math.abs(target) > total) return 0;4const goal = (total + target) / 2, dp = new Array(goal + 1).fill(0);5dp[0] = 1;6for (const x of nums)7for (let s = goal; s >= x; s--) dp[s] += dp[s - x];8return dp[goal];9}
Need a '+' subset summing to (5 + 3) / 2 = 4.
Space: play/pause · ←/→: step