Backtracking
Retrieval: the four decisions
Two problems rebuilt cold, plus the checklist that determines any backtracking solution.
Key idea
Answer these and the code writes itself
What is a choice at each level? An item, a direction, a cut point, a placement.
What does the next call receive? The same index for reuse, the next index for single use, zero or a used-set when order matters.
What state changes, and is every change undone? Count them. Most bugs in this unit are an uncounted change.
What makes a branch impossible, and can it be detected before descending? That is the pruning, and it is the difference between a search that finishes and one that does not.
Tip
And the one that is always the same
Store a copy of the result, never the working list. If every answer comes back identical or empty, that is why.
Which decision is wrong here?
A search for all distinct combinations from a list with repeated values returns duplicates. Sorting is present and the copy is correct. Which decision is most likely wrong?
Subsets II, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.
Find Median from Data Stream, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.