One-dimensional Dynamic Programming
Each item once
The unit's last shape, and the one that most often hides behind a question about something else.
Key idea
Recognizing the shape
A problem asks whether a collection can be divided into two parts with equal totals. There is no obvious table anywhere in that sentence, which is why it is worth taking apart.
If the two parts are equal, each is half the overall total. So the question is whether some subset reaches exactly half, and the other part follows automatically. If the overall total is odd, no split exists and you are done before starting.
That reduction is the entire difficulty. What remains is a standard subset-sum.
Why it works
Reachable totals, using each item at most once
The state is a total and the answer is whether it is reachable. That looks identical to the coin problem, and the difference is that each item may be used only once, which the coin loop does not enforce.
The cleanest way to handle it is to process one item at a time and, for each, update which totals become reachable by adding it. Since each item is considered in exactly one pass, it cannot be reused.
Why it works
Why the set version cannot double-use
The comprehension reads reachable as it was at the start of the statement and unions the result afterward, so a value added in this pass cannot be extended again in the same pass.
The array version has the same requirement and enforces it differently: iterate the totals downward, so a cell updated in this pass is never read again during it. That is the opposite direction from the unlimited-reuse version in the earlier lesson, and the direction is precisely what encodes once versus many times.
Two loops that differ only in direction and mean entirely different problems is worth pausing on. If a subset-sum solution allows reusing an item, check the loop direction first.
Tip
The second check proves the direction matters
With a single 3 and a target of 6, the answer must be False, because the item may be used once. An upward loop would mark 3 reachable and then, still in the same pass, use that to mark 6, reusing the item.
That one test distinguishes the two versions. Any subset-sum solution should be run against it.
Edge cases
An empty collection
An empty collection has a total of zero, which is even, and the target is zero, which is reachable with nothing. So it splits evenly into two empty halves.
Some problem statements exclude that case. It is worth a moment to decide what the specification wants rather than letting the code decide for you.
Cost
Cost
The array version is O(items times target) time and O(target) space. As with the coin problem, the target is a value rather than a length, so a large target is expensive even for a short input.
This is called pseudo-polynomial for that reason: it is polynomial in the numeric value rather than in the size of the input. Naming that is a genuinely strong signal, and it is the honest answer to why this approach is fine for the stated constraints and would not be in general.
Predict the output: which loop direction reuses an item
One item of size 3 is offered to a table of reachable totals, once upward and once downward. Type the two lines it prints.
Partition Equal Subset 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.