All Paths From Source to Target: Coding Problem

Source: Dev.to

Problem Overview

The “All Paths From Source to Target” problem asks you to find every possible path from a starting node to a destination node in a directed graph.
The graph is typically provided as an adjacency list, where each node points to a list of neighbors it can reach directly. Your job is to return all valid paths that begin at the source and end at the target, with each path listed as a sequence of nodes in the order they are visited.

This problem is not about finding the shortest path or merely determining reachability; it is explicitly about enumeration. You must generate every valid route, which changes the nature of the solution completely. Instead of optimizing distance, you are exploring a search space of possibilities.

Why Not BFS

• Breadth‑first search (BFS) is excellent when you want the shortest path in an unweighted graph because it explores by distance layers.
• Here, distance is not the goal, and exploring level by level provides no meaningful advantage.
• BFS tends to require storing many partial paths at once, increasing memory usage significantly. Since path enumeration can already create a large number of candidates, you generally want an approach that keeps memory under control.

DFS with Backtracking

Depth‑first search (DFS) fits this problem naturally because it explores one path to completion before moving on to the next.

1. Start at the source.
2. Pick a neighbor, continue forward, and keep going until you either reach the target or run out of moves.
3. When you reach the target, record the current path as one valid answer.
4. When you hit a dead end, backtrack and try a different neighbor.

Backtracking Mechanism

• Maintain a current path list as you move forward through the graph.
• When you choose a neighbor, add it to the path.
• When you return from exploring that choice, remove it.

This ensures the path list always represents exactly the route you’re currently exploring, avoids creating a separate copy at every step, and keeps the algorithm cleaner and more efficient. It also guarantees systematic generation without accidental carryover from previous explorations.

Handling Cycles

In general directed graphs, cycles can create infinite numbers of paths if revisiting nodes is allowed. Many versions of this problem implicitly use a directed acyclic graph (DAG), which removes the cycle risk and guarantees a finite set of paths.

If cycles are possible:

• Use a visited constraint within the current recursion stack to prevent revisiting nodes in the same path exploration.
• Do not use a global visited set, because that would incorrectly eliminate valid paths that revisit a node in a different route.

Complexity Analysis

• Time complexity is dominated by the number of paths and their lengths, since you must actually output all paths. In dense acyclic graphs, the number of paths can grow exponentially, and no algorithm can avoid that cost when the output itself is exponential.
• Space complexity is driven by the recursion depth and the current path being built, proportional to the length of the longest path. Additional space is required to store the output paths, which is unavoidable.

Why This Problem Is Useful

• It tests whether candidates understand the difference between searching for a single solution and enumerating all solutions.
• It checks backtracking fundamentals, such as maintaining mutable state safely and undoing changes correctly.
• Recognizing that output size drives runtime demonstrates algorithmic maturity.
• The pattern of “DFS with backtracking” extends beyond graph traversal to combinatorics, constraint satisfaction problems, and other recursive enumeration tasks.

Being able to clearly explain why DFS is preferred, how backtracking maintains the current route, and how cycles should be handled without losing valid paths showcases strong algorithmic reasoning and makes this problem an excellent exercise in systematic enumeration and recursive search.