-**Base case**: Equivalent to the termination condition. After reaching the base case, the result can be returned without recursive calls to prevent infinite loops.

-**Recursive step**: The step by which the problem gradually approaches the "base case".

1. Initialize an empty list`paths` to store all the valid paths found from source to target.

2. Define a recursive Depth-First Search (DFS) function, say`dfs`, that takes the current`node` and the`currentPath` (a list of nodes visited so far to reach the current node) as input.

3. Inside the`dfs` function:

a. Create a new path list by appending the current`node` to the`currentPath`. Let's call this`newPath`.

b. Check if the current`node` is the target node (`n - 1`, where`n` is the total number of nodes).

i. If it is the target node, it means we've found a complete path. Add`newPath` to the main`paths` list and return from this recursive call.

c. If the current`node` is not the target node, iterate through all`neighbor` nodes accessible from the current`node` (i.e., iterate through`graph[node]`).

i. For each`neighbor`, make a recursive call to`dfs` with the`neighbor` as the new current node and`newPath` as the path taken to reach it (`dfs(neighbor, newPath)`).

4. Start the process by calling the`dfs` function with the source node`0` and an empty initial path (`dfs(0, [])`).

5. After the initial`dfs` call completes, return the`paths` list containing all discovered paths.

- Time complexity:`Too complex`.

**Depth-First Search (DFS)** is a classic graph traversal algorithm characterized by its**"go as deep as possible"** approach when exploring branches of a graph. Starting from the initial vertex, DFS follows a single path as far as possible until it reaches a vertex with no unvisited adjacent nodes, then backtracks to the nearest branching point to continue exploration. This process is implemented using**recursion** or an**explicit stack (iterative method)**, resulting in a**Last-In-First-Out (LIFO)** search order. As a result, DFS can quickly reach deep-level nodes far from the starting point in unweighted graphs.

**Comparison with BFS**:

1.**Search Order**: DFS prioritizes depth-wise exploration, while Breadth-First Search (BFS) expands layer by layer, following a**First-In-First-Out (FIFO)** queue structure.

2.**Use Cases**: DFS is better suited for strongly connected components or backtracking problems (e.g., finding all paths in a maze), whereas BFS excels at finding the shortest path (in unweighted graphs) or exploring neighboring nodes (e.g., friend recommendations in social networks).

**Unique Aspects of DFS**:

-**Incompleteness**: If the graph is infinitely deep or contains cycles (without visited markers), DFS may fail to terminate, whereas BFS always finds the shortest path (in unweighted graphs).

-**"One-path deep-dive"** search style makes it more flexible for backtracking, pruning, or path recording, but it may also miss near-optimal solutions.

In summary, DFS reveals the vertical structure of a graph through its depth-first strategy. Its inherent backtracking mechanism, combined with the natural use of a stack, makes it highly effective for path recording and state-space exploration. However, precautions must be taken to handle cycles and the potential absence of optimal solutions.

1. Initialize an empty list`paths` to store all valid paths found from the source to the target.

2. Create a mutable list`path` to track the current path being explored, initially containing only the source node`0`.

3. Implement a recursive DFS function that explores paths using backtracking:

- Base case: If the current node is the target node (`n-1`), make a copy of the current path and add it to the`paths` list.

- Recursive step: For each neighbor of the current node:

- Add the neighbor to the current path.

- Recursively call the DFS function with this neighbor.

- After the recursive call returns, remove the neighbor from the path (backtrack).

4. Start the DFS from the source node`0`.

5. Return the collected`paths` after the DFS completes.

- Time complexity:`Too complex`.

- Space complexity:`Too complex`.

classSolution:

defallPathsSourceTarget(self,graph: List[List[int]]) -> List[List[int]]:

self.paths= []

self.graph= graph

self.path= [0]# Important

self.dfs(0)

returnself.paths

defdfs(self,node):

if node==len(self.graph)-1:

self.paths.append(self.path.copy())# Important

for neighborinself.graph[node]:

self.path.append(neighbor)# Important

self.dfs(neighbor)

self.path.pop()# Important

classSolution {

privateList<List<Integer>> paths=newArrayList<>();

privateList<Integer> path=newArrayList<>(List.of(0));// Important - start with node 0

privateint[][] graph;

publicList<List<Integer>>allPathsSourceTarget(int[][]graph) {

this.graph= graph;

dfs(0);

return paths;

}

privatevoiddfs(intnode) {

if (node== graph.length-1) {// Base case

paths.add(newArrayList<>(path));// Important - make a copy

return;

}

for (int neighbor: graph[node]) {// Recursive step

path.add(neighbor);// Important

dfs(neighbor);

path.remove(path.size()-1);// Important - backtrack

}

}

}

classSolution {

public:

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {

_graph = graph;

_path = {0}; // Important - start with node 0

vector<vector<int>> _paths;

vector<vector<int>> _graph;

vector<int> _path;

voiddfs(int node) {

if (node ==_graph.size() - 1) { // Base case

_paths.push_back(_path); // Important - copy is made automatically

return;

}

};

{

privateIList<IList<int>>paths=newList<IList<int>>();

privateList<int>path=newList<int> {0 };// Important - start with node 0

privateint[][]graph;

publicIList<IList<int>>AllPathsSourceTarget(int[][]graph)

{

this.graph=graph;

Dfs(0);

returnpaths;

}

privatevoidDfs(intnode)

{

if (node==graph.Length-1)

{// Base case

paths.Add(newList<int>(path));// Important - make a copy

return;

}

foreach (intneighboringraph[node])

{// Recursive step

path.Add(neighbor);// Important

Dfs(neighbor);

path.RemoveAt(path.Count-1);// Important - backtrack

}

}

}

funcallPathsSourceTarget(graph [][]int) [][]int {

paths:= [][]int{}

path:= []int{0}// Important - start with node 0

vardfsfunc(int)

dfs =func(nodeint) {

if node ==len(graph) -1 {// Base case

paths =append(paths,append([]int(nil), path...))

}

for_,neighbor:=range graph[node] {// Recursive step

path =append(path, neighbor)// Important

dfs(neighbor)

path = path[:len(path) -1]// Important - backtrack

}

}

dfs(0)

return paths

}

defall_paths_source_target(graph)

@paths= []

@graph= graph

@path= [0]# Important - start with node 0

dfs(0)

defdfs(node)

if node==@graph.length-1# Base case

@paths<<@path.clone# Important - make a copy

@graph[node].eachdo |neighbor|# Recursive step

@path<< neighbor# Important

dfs(neighbor)

@path.pop# Important - backtrack

Dear LeetCoders! For a better LeetCode problem-solving experience, please visit website[LeetCodePython.com](https://leetcodepython.com): Dare to claim the best practices of LeetCode solutions! Will save you a lot of time!

Original link:[797. All Paths From Source to Target - LeetCode Python/Java/C++/JS code](https://leetcodepython.com/en/leetcode/797-all-paths-from-source-to-target).