medium

All Paths From Source to Target

List every route from the first node to the last in a directed graph with no cycles, using backtracking to undo one move at a time.

1. Define the problem

All Paths From Source to Target

You are given a directed graph with n nodes numbered 0 to n - 1, written as an adjacency list: graphi holds the nodes you can move to from node i. The graph has no cycles , so you can never come back to a node you have left. Return every path from node 0 to node n - 1, in any order. Walk forward one node at a time, keeping the path so far in a list. When you reach the last node, save a copy of that path. Then step back, remove the last node, and try the next option. That stepping back is called backtracking.

Constraints

  • 2 ≤ n ≤ 15
  • graphi never contains i, so no node points at itself
  • Every edge goes from a lower number to a higher one, which is what keeps the graph acyclic
  • There is always at least one path from 0 to n - 1 in the tests here

Example

Inputgraph = [[1, 2], [3], [3], []]
Output[[0, 1, 3], [0, 2, 3]]

Explanation From node 0 you can go to 1 or 2, and both of those lead to node 3. That gives exactly two routes from 0 to 3.

2. Know the words first

In plain terms

Directed graph
A graph whose edges are one-way. Being able to go from 0 to 1 says nothing about going from 1 to 0.
Acyclic
Having no cycles, so no route ever returns to a node it already left. That is why this search needs no visited list.
Backtracking
Exploring one option fully, then undoing the last move and trying the next one. Here the undo is removing the last node from the path.
Path copy
Saving a snapshot of the path list. Without the copy, every saved answer would point at the same list, which keeps changing.
3. Visualize the solution

The path being built right now, one cell per position along it

The path being built right now, one cell per position along it
Statusinit

Every path starts at node 0, so the first position is filled and the rest are empty.

What happens in this step

graph = [[1, 2], [3], [3], []]
target = 3
path = [0]
results = []

Node 0 leads to node 1 and node 2, so there are two branches to try.
Step 1 of 6

Steps to visualize

  1. The row is the current path, not the graph. Cell p0 is the first node on the path, p1 the second, and so on.
  2. A dash means that position is not filled yet.
  3. Every forward move writes a node into the next free position.
  4. Reaching the last node of the graph means the path is complete, so a copy of it is saved.
  5. Backtracking clears the last position and the search tries the next option from the node before it.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The path being built right now, one cell per position along it
Statusinit

Every path starts at node 0, so the first position is filled and the rest are empty.

What happens in this step

graph = [[1, 2], [3], [3], []]
target = 3
path = [0]
results = []

Node 0 leads to node 1 and node 2, so there are two branches to try.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function allPathsSourceTarget(graph) {
  const target = graph.length - 1;
  const results = [];
  const path = [0];

  function walk(node) {
    if (node === target) {
      results.push(path.slice());
      return;
    }

    for (const next of graph[node]) {
      path.push(next);
      walk(next);
      path.pop();
    }
  }

  walk(0);

  return results;
}
Time
O(2^n * n) in the worst case, because that many paths can exist
Space
O(n) for the path, not counting the answer
6. Test cases

Test cases

InputExpectedCovers
graph = [[1, 2], [3], [3], []][[0, 1, 3], [0, 2, 3]]example from the docstring
graph = [[4, 3, 1], [3, 2, 4], [3], [4], []][[0, 4], [0, 3, 4], [0, 1, 3, 4], [0, 1, 2, 3, 4], [0, 1, 4]]a denser graph with five different routes
graph = [[1], []][[0, 1]]smallest graph, one edge and one route
graph = [[]][[0]]degenerate case where the start is already the finish
graph = [[1, 2, 3], [2], [3], []][[0, 1, 2, 3], [0, 2, 3], [0, 3]]routes of three different lengths from the same start
graph = [[1, 3], [2], [3], []][[0, 1, 2, 3], [0, 3]]a long chain next to a direct jump

Keep reading