The depth-first search pattern: exploring every path
When the question is about paths themselves (all of them, or the ones with a property), search depth-first and undo each step on the way back.
What the pattern is
A plain traversal marks a node once and never visits it again; that is enough to know what is reachable. Some problems ask about the paths instead: list every route from A to B, count the routes whose weights add to a target, find a route that visits every node once. Two different paths may share a node, so a node cannot be marked for good. It is marked while it is on the current path and unmarked when the search backs out of it. This is backtracking on a graph.
Depth-first search over paths
explore(u, path)
- Add u to
onPathand topath. - If u is the target (and the path satisfies the condition), record or count the path.
- Otherwise, for each neighbour v not in
onPath:explore(v, path). - Remove u from
pathandonPath(backtrack).
How to recognise it
- The output is a set of paths, or a count of paths, rather than one distance or one yes/no.
- The words "all", "every possible", "simple path", "visit each exactly once", "route whose total equals".
- Small inputs: n up to 10–20 nodes. The number of paths can grow exponentially, and the constraints say the problem setter knows it.
If the graph is a DAG (as in "all paths from 0 to n − 1" on LeetCode), no node can repeat on a path, so onPath is not even needed. Keep it anyway when you are not sure the input is acyclic.
Worked example: every path from 0 to 4
On the directed graph below, list every path from 0 to 4. Watch nodes leave the path when the search backs out of them.
Backtracking from 0; neighbours tried in increasing order.
-
Step 1 / 18current path00paths foundnone yet0
Start at 0, the only node on the path.
-
Step 2 / 18current path0011paths foundnone yet0
Extend the path to 1.
-
Step 3 / 18current path001122paths foundnone yet0
Extend the path to 2.
-
Step 4 / 18current path00112233paths foundnone yet0
Extend the path to 3.
-
Step 5 / 18current path0011223344paths found012340
Reached 4: record the path 0 → 1 → 2 → 3 → 4. Then back up to look for others.
-
Step 6 / 18current path001122paths found012340
Every way on from 3 is explored: remove 3 from the path so other paths may use it.
-
Step 7 / 18current path00112243paths found01234001241
Reached 4: record the path 0 → 1 → 2 → 4. Then back up to look for others.
-
Step 8 / 18current path0011paths found01234001241
Every way on from 2 is explored: remove 2 from the path so other paths may use it.
-
Step 9 / 18current path001132paths found01234001241
Extend the path to 3.
-
Step 10 / 18current path00113243paths found0123400124101342
Reached 4: record the path 0 → 1 → 3 → 4. Then back up to look for others.
-
Step 11 / 18current path0011paths found0123400124101342
Every way on from 3 is explored: remove 3 from the path so other paths may use it.
-
Step 12 / 18current path00paths found0123400124101342
Every way on from 1 is explored: remove 1 from the path so other paths may use it.
-
Step 13 / 18current path0021paths found0123400124101342
Extend the path to 2.
-
Step 14 / 18current path002132paths found0123400124101342
Extend the path to 3.
-
Step 15 / 18current path00213243paths found012340012410134202343
Reached 4: record the path 0 → 2 → 3 → 4. Then back up to look for others.
-
Step 16 / 18current path0021paths found012340012410134202343
Every way on from 3 is explored: remove 3 from the path so other paths may use it.
-
Step 17 / 18current path002142paths found0123400124101342023430244
Reached 4: record the path 0 → 2 → 4. Then back up to look for others.
-
Step 18 / 18current path00paths found0123400124101342023430244
Every way on from 2 is explored: remove 2 from the path so other paths may use it. Search finished: 5 paths.
current nodeon the current pathtarget
Exponential in the worst case: a graph can have more than (n − 2)! simple paths between two nodes. That is why these problems come with small n, and why pruning (stop as soon as a partial sum exceeds the target, for instance) matters.
The problems in this module: