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 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 this is a graph traversal and enumeration problem
The moment a problem asks for “all paths,” you should expect exponential growth in the number of outputs in the worst case. That does not mean the problem is unsolvable; it means the algorithm must be structured to explore the graph systematically and produce paths efficiently without missing or duplicating any.
The right mental model is that each node represents a decision point. From the source, you can choose any outgoing edge, and from there you choose again, until you eventually reach the target. Every distinct sequence of choices is a distinct path.
Why breadth-first search is not the best fit
Breadth-first search 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 does not provide a meaningful advantage.
More importantly, BFS tends to require storing many partial paths at once, which can increase memory usage significantly. Since path enumeration can already create a large number of candidates, you generally want an approach that keeps memory under control.
Want to explore more coding problem solutions? Check out the Single Number III and Binary Tree Paths.
Depth-first search as the natural strategy
Depth-first search fits this problem naturally because it explores one path to completion before moving on to the next. You start at the source, pick a neighbor, continue forward, and keep going until you either reach the target or run out of moves. When you reach the target, you record the current path as one valid answer. When you hit a dead end, you backtrack and try a different neighbor.
This aligns perfectly with how you would manually list all routes: commit to a route, finish it, then return to the last branching point and try another option.
Backtracking is the key to generating multiple paths
The mechanism that makes DFS work for “all paths” is backtracking. As you move forward through the graph, you maintain a current path list. When you choose a neighbor, you add it to the path. When you return from exploring that choice, you remove it. This ensures the path list always represents exactly the route you’re currently exploring.
Backtracking prevents you from creating a separate path copy at every step, which keeps the algorithm cleaner and more efficient. It also ensures paths are generated in a systematic way without accidental carryover from previous explorations.
Why cycles matter and when they don’t
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, which removes the cycle risk and guarantees a finite set of paths.
If cycles are possible, you need a visited constraint within the current recursion stack to prevent infinite loops. The important nuance is that you do not want a global visited set that blocks revisiting nodes across different paths, because that would incorrectly eliminate valid paths. You only want to prevent revisiting nodes within the same path exploration.
Why the approach is correct
The correctness of DFS with backtracking comes from exhaustive exploration. From every node, you try every outgoing edge, and you continue recursively until reaching the target. Every valid path corresponds to a unique sequence of recursive choices, so it will be generated exactly once.
Because you only record a path when you reach the target, every recorded result is guaranteed to be valid. Because you explore every choice from every reachable node, no valid path is missed.
Time and space complexity considerations
The 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 if it is required to list them all.
Space complexity is driven by the recursion depth and the current path being built. This is proportional to the length of the longest path. Additional space is used to store the output paths, which again is unavoidable because the problem explicitly asks for all of them.
Why this problem is popular in interviews
This problem is commonly used in interviews because it tests whether candidates understand the difference between searching for one solution and enumerating all solutions. It also checks backtracking fundamentals, such as maintaining a mutable path state safely and undoing changes correctly.
It’s also a good way to see whether someone can reason about complexity honestly. Recognizing that output size drives runtime is a key piece of algorithmic maturity.
What this problem teaches beyond graphs
Beyond graph traversal, “All Paths From Source to Target” teaches a broader pattern: when you need to generate every valid arrangement under a set of rules, DFS with backtracking is often the cleanest approach. You see this same structure in combinatorics, constraint satisfaction problems, and recursive enumeration tasks.
If you can clearly explain why DFS is preferred here, how backtracking maintains the current route, and how cycles should be handled without losing valid paths, you demonstrate strong algorithmic reasoning. That depth of understanding makes this problem an excellent exercise in systematic enumeration and recursive search.
Top comments (0)