All Paths From Source to Target

All Paths From Source to Target

What is this problem about?

The "All Paths From Source to Target interview question" asks you to find every possible path from the starting node (usually node 0) to the final node (node $n-1$) in a Directed Acyclic Graph (DAG). Unlike problems where you just need to find the shortest path or check if a path exists, this challenge requires an exhaustive search of the entire graph to list out every single route.

Why is this asked in interviews?

Companies like Microsoft, Meta, and Google use the "All Paths From Source to Target coding problem" to test a candidate's proficiency with graph traversal and backtracking. Since the graph is guaranteed to be a DAG, you don't have to worry about infinite loops, which allows the interviewer to focus on how you manage state and build up your result list during recursion.

Algorithmic pattern used

This problem is a perfect fit for the Backtracking and Depth-First Search (DFS) patterns.

1. Explore: Start from node 0.
2. State Management: Keep a "current path" list. Add the current node to it.
3. Base Case: If the current node is the target (node $n-1$), add a copy of the current path to your global results list.
4. Recurse: For every neighbor of the current node, move to that node and repeat the process.
5. Backtrack: After exploring all paths from a neighbor, remove the current node from the "current path" list so you can explore other branches from the previous node.

Example explanation

Graph: [[1, 2], [3], [3], []] (Nodes 0, 1, 2, 3)

• Start at 0: Path [0]. Neighbors: 1, 2.
• Move to 1: Path [0, 1]. Neighbor: 3.
• Move to 3: Path [0, 1, 3]. Target reached! Save path.
• Backtrack to 1, then back to 0.
• Move to 2: Path [0, 2]. Neighbor: 3.
• Move to 3: Path [0, 2, 3]. Target reached! Save path. Result: [[0, 1, 3], [0, 2, 3]].

Common mistakes candidates make

• Not copying the path: Adding a reference to the "current path" list into the result instead of a deep copy. When the recursion backtracks, the paths in your result list will end up empty or incorrect.
• Using BFS inefficiently: While BFS can work, it's generally more memory-intensive for finding "all paths" compared to the elegant recursion of DFS.
• Forgetting Backtracking: Failing to remove the node from the path after the recursive call, which leads to bloated and incorrect paths.

Interview preparation tip

Practice backtracking with simple problems first. Understanding the "choose, explore, un-choose" lifecycle is critical. For graph problems, always check if the graph is a DAG—if it is, you can often simplify your logic by omitting complex cycle-detection mechanisms.