Signs That Reach the Target
Put a + or a - in front of every number, then add them up. Count the
assignments that total exactly t.
1 1 1 1 1 with t = 3 -> 5 one minus, in any of five places
Every number must get a sign, and assignments are counted separately even when
they produce the same arrangement of values. A zero is worth noting: +0 and
-0 are different assignments with the same effect, so [0, 0] reaching 0 has
four answers, not one.
Trying all 2^n sign patterns is exponential.
The state is the running total, and the transition takes BOTH branches because they are disjoint sets of assignments rather than competing options:
ways(i, sum) = ways(i+1, sum + a[i]) + ways(i+1, sum - a[i])
Sums can be negative, which is what makes the state space awkward and is why a
map keyed by the running total is the natural representation. An array needs an
offset of sum of all values to keep every index non-negative, and getting that
offset wrong is the usual source of a silent wrong answer.
There is a reduction worth knowing. If the positives total P and the negatives
total N, then P - N = t and P + N = S, so P = (S + t) / 2. So the question
is "how many subsets sum to (S + t) / 2", which is problem #229 counting rather
than deciding, and it has no negative indices at all. It also shows immediately
that S + t being odd, or |t| > S, means zero.