Target Sum in TypeScript: Count the Signs, Including Zeroes

Zero is the most revealing input in Target Sum. Adding it doesn't change a total, and subtracting it doesn't change a total either. Yet those are two different sign assignments, so a counting algorithm has to preserve both.
That small distinction tells us what we're counting. We aren't collecting distinct numeric results, and we aren't collecting distinct values from the input. We're counting the choices made at individual positions. If the state loses those choices, the answer may look tidy and still be wrong.
In LeetCode's Target Sum problem, every non‑negative input value receives either a plus or a minus sign. We need the number of assignments whose result equals a supplied target. I'll turn that into a subset‑counting problem, then use the zero case to check that the transformation hasn't discarded anything.
Start with the Obvious Search
For each position, a recursive search can try the positive and negative versions of its value. After the final position, it counts one result if the accumulated total matches the target. With n positions, that explores 2^n complete assignments.
There is nothing conceptually wrong with this solution. It's also an excellent small‑input reference implementation, because its behaviour follows the question directly. The repeated work comes from different assignment prefixes reaching the same position and current total.
One optimisation would keep a map from each reachable signed total to its number of assignments. For every input value, we would build a fresh map containing the positive and negative transitions. That formulation works well and makes zero doubling particularly obvious: both transitions arrive at the same key and their counts add.
Here, the non‑negative input promise lets us use a more compact target‑indexed table instead. I prefer deriving that table rather than treating it as a memorised conversion.
Separate the Positive and Negative Groups
Let P be the sum of values assigned a plus sign, and N the sum of values assigned a minus sign. Let S be the sum of every input value. Then P + N = S, because every position belongs to one group, and P - N = target, because that's the expression's result.
Adding the two equations gives 2P = S + target. We therefore need to count subsets of positions whose values sum to (S + target) / 2. Choosing such a subset completely determines the signs: its members get plus signs and every remaining position gets a minus sign.
Two quick rejection tests follow. If the target's magnitude exceeds S, no assignment can reach it. If S + target is odd, the required positive total isn't an integer. Both conditions can return zero before allocating a table.
For 1, 2, 3 and target 2, the total is six and the required positive sum is four. Only the positions containing one and three make that sum, giving +1 -2 +3. For target one, the parity check rejects the request immediately.
The transformation doesn't require the target itself to be positive. A negative target simply produces a smaller positive‑group sum. The magnitude check ensures that this sum never becomes negative.
Count Subsets of Positions
Let ways[s] contain the number of subsets, among positions processed so far, whose values sum to s. Initially ways[0] = 1, representing the empty subset, and every other count is zero.
When an item has value v, every previously available subset summing to s - v can produce a new subset summing to s by including this position. Subsets already counted at s remain valid without it. We therefore add the source count to the existing destination count.
As with selecting individual items in a knapsack, destinations run downwards. For a positive value, the source at s - v hasn't been updated during the current pass, so the current occurrence cannot be used more than once.
Repeated values remain separate occurrences. For 1, 1, 1 and target one, there are three assignments: the minus sign can occupy any of the three positions. Converting the input into a set would collapse that distinction and break the answer.
Zeroes Double the Right Cells
When v is zero, the source and destination are the same cell. The update becomes ways[s] += ways[s], doubling its previous value once during that zero's pass. That is exactly right: each previous subset can either include this zero position or omit it.
Take 0, 0, 1 with target one. The required positive sum is one. The table begins with one way to make zero, becomes two after the first zero, becomes four after the second, and transfers four ways to sum one when the final value is processed.
Those four choices correspond to independently choosing either sign for each zero, with a plus sign on the one. Nothing special needs bolting onto the algorithm. The ordinary update already models the choice correctly, provided the lower bound allows a zero value through.
Skipping zeroes as an optimisation would therefore remove real answers. It's an efficient way to become confidently wrong.
Complete TypeScript Implementation
const findTargetSumWays = (nums: number[], target: number): number => {
const total = nums.reduce((sum, value) => sum + value, 0);
if (Math.abs(target) > total || (total + target) % 2 !== 0) return 0;
const positiveTotal = (total + target) / 2;
const ways: number[] = Array(positiveTotal + 1).fill(0);
ways[0] = 1;
for (const value of nums) {
for (let sum = positiveTotal; sum >= value; sum -= 1) {
ways[sum] += ways[sum - value];
}
}
return ways[positiveTotal];
};For a required positive total P, the time is O(n × (P + 1)), including the zero‑target case, and the additional storage is O(P + 1). There is no input mutation and no recursive call stack.
The official constraints limit the input to twenty positions and its total to 1,000. There are at most 2^20 sign assignments, so every intermediate count and final answer fits exactly in a JavaScript number. That argument is stronger than merely observing that the examples produce small answers.
Outside those constraints, counts can grow rapidly. If this were a general counting utility, I would revisit the numeric type and the table size together. Changing the return type to bigint alone doesn't make a huge target practical to index.
Check the Algebra with a Different Algorithm
For small inputs, enumerate all sign assignments and count exact matches. Compare that result with the subset implementation across arrays containing zeroes, repeated values, and a small range of positive values. This reference tests the algebraic reduction as well as the table update.
Keep explicit cases for a target outside the total, the wrong parity, all zeroes targeting zero, and all zeroes targeting a non‑zero value. Twenty zeroes targeting zero should return 1,048,576; a single one targeting zero should return zero.
There are useful properties too. Negating the target must preserve the answer, because flipping every sign pairs assignments one‑to‑one. Reordering the values also preserves the count. Appending a zero doubles it. These follow from the problem, so they provide checks that don't depend on the particular table layout.
My guide to choosing dynamic‑programming state discusses this habit of deciding what one cell counts before selecting its data structure. My Decode Ways walkthrough shows a different counting problem where zero changes which transitions are legal, rather than simply doubling a count.
Wrapping Up
The useful reduction is a correspondence between sign assignments and subsets of positions. Once that correspondence is clear, the parity check, descending updates, repeated values, and zero handling all follow from it.
I would keep the sign‑enumeration reference beside any later optimisation. It's small, readable, and happily oblivious to the algebra, which is precisely why it makes a useful second opinion.