Checkpoint: recursion and graphs
Transfer: six problems you have not seen
Recursion, generation, two traversals, connectivity, and a design. No labels.
Key idea
Four units, one idea
It is worth seeing how little actually separates the last four units. Every one of them explores a structure by taking a step, remembering something, and continuing.
Backtracking remembers the current path and forgets it on the way out. Graph traversal remembers every node seen and never forgets. A trie is the thing being explored rather than the explorer. The weighted algorithms replace the queue with a heap so the cheapest option comes out next.
So the questions to ask a new problem are: what is a node, what is a step, what has to be remembered, and does the order of exploration matter.
Tip
One note
Two of the six below are grid searches wanting different things from each other, and one of those two is not a plain breadth-first search. Read both carefully before deciding they are the same problem.
Nested Weight Sum
Sum integers nested inside lists, weighting each by how deeply it sits. Decide what a node needs to know from above before you pick a signature.
Sentence Combinations
Produce every sentence formed by taking one word from each list, in order. The branching factor comes from the data rather than being fixed.
Shortest Route from Any Start
Find the fewest steps from any of several starting cells to the target. Running one search per start is the obvious approach; there is a better one you have already written.
Farthest District
Report how long the farthest district takes to reach any hospital. Two things to get right: the search shape, and what to report when somewhere cannot reach one at all.
Count Unreachable Pairs
Count pairs of nodes that sit in different components. Enumerating pairs is far too slow; work out what the component sizes alone tell you.
Key-Value Store with Prefix Queries
Support insert, delete, and a query returning everything under a prefix. Deletion is the part the reading did not cover; decide what happens to a node once nothing beneath it remains.