Two-dimensional Dynamic Programming
Restating a problem into one you have solved
Some problems are a solved problem behind a change of variables. Finding the change is the work.
Key idea
The setup
Every value must be assigned a plus or a minus, and the signed total must equal a target. Count the assignments that work.
The direct approach is a table indexed by position and running total, with the total offset to keep indexes non-negative since it can go below zero. That works and is a little awkward.
Why it works
Two groups, and simple algebra
Every assignment splits the values into a positive group and a negative group. Call their sums P and N. Then P minus N is the target, and P plus N is the overall total, which is fixed.
Adding those two equations gives twice P equals the target plus the overall total, so P is half of that. The question becomes: how many subsets sum to that value?
That is a counting subset-sum, which you can already write. No offsets and no negative indexes.
The algebra is the whole lesson, so here it is on a concrete input, stopping at the point where the problem has been replaced.
Gotcha
Both guards are load-bearing
If the target exceeds the overall total in magnitude, no assignment reaches it and the answer is zero. Without that check the computed subset target is out of range and the table is built wrong or raises.
If the total plus the target is odd, the required subset sum is not a whole number, so no assignment exists. Integer division would silently round and produce a plausible count for an impossible request.
Both cases appear in test suites and neither is obvious from the algebra alone. Deriving a formula does not remove the need to ask when it is undefined.
Tip
The downward loop again
Each value gets one sign, so it may be used at most once, which is the downward loop from U14's subset-sum lesson.
That single detail is the difference between this and the previous lesson's combination counting, where the loop ran upward because pieces were unlimited. Two adjacent lessons, opposite directions, and the reason is the same each time.
Edge cases
Zeros in the input
A value of zero can take either sign without changing anything, so each zero doubles the count. The subset-sum formulation handles this correctly and automatically, because a zero can be included or not and both produce the same sum.
The direct table version also handles it, and it is worth checking rather than assuming. An input of all zeros with a target of zero is a good test: the answer should be two to the number of zeros.
The habit worth taking
When a problem involves choices with opposite effects, or a difference that must hit a target, try writing the two groups as unknowns and solving. It frequently collapses into a standard problem.
Five minutes of algebra beat an hour of building a table around an awkward state. Do the algebra first.
Predict the output: when the restated problem has no answer
The algebra turns a sign assignment into a subset sum. Three requests are checked against it before any table is built. Type the three lines it prints.
Target Sum
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.