431. 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.

Constraints - `1 ≤ n ≤ 20` - `0 ≤ value ≤ 1000` - `-20000 ≤ t ≤ 20000` - The answer fits in a signed 64-bit integer.