## Similar Problems

Similar Problems not available

# All Paths From Source To Target - Leetcode Solution

## Companies:

LeetCode: All Paths From Source To Target Leetcode Solution

Difficulty: Medium

Topics: graph backtracking depth-first-search breadth-first-search

Problem Statement:

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1, and return them in any order.

The graph is represented by a list of edges, where edges[i] = [ai, bi] denotes a directed edge from node ai to node bi. Note that the edges are directed, so a pair [ai, bi] does not imply a pair [bi, ai].

Example:

Input: graph = [[1,2],[3],[3],[4],[]] Output: [[0,1,3,4],[0,2,3,4]] Explanation: There are two paths: 0 -> 1 -> 3 -> 4 and 0 -> 2 -> 3 -> 4.

Solution:

Approach:

We can use depth-first search to traverse all the possible paths in the graph. The idea is to start from the source node (0) and visit all its neighbors recursively until we reach the target node (n-1). We can keep track of the path we are taking in a list and append it to our answer list once we reach the target node. We can continue the search until all the possible paths are explored.

Algorithm:

- Create an empty list called 'result' to store all possible paths.
- Create an empty list called 'path' to store the current path.
- Define a recursive function called 'dfs' with input parameters as the current node and the graph.
- Inside the 'dfs' function: a. Append the current node to the 'path' list. b. If the current node is the target node (n-1), append the 'path' list to the 'result' list and return. c. For each neighbor of the current node, call the 'dfs' function recursively with the neighbor node as the current node. d. Remove the current node from the 'path' list (backtracking).
- Call the 'dfs' function with the initial node as 0.
- Return the 'result' list.

Code:

class Solution: def allPathsSourceTarget(self, graph): """ :type graph: List[List[int]] :rtype: List[List[int]] """ result = [] path = []

```
def dfs(node, graph):
# Append the current node to the path list
path.append(node)
# If the current node is the target node, append the path list to the result list
if node == len(graph) - 1:
result.append(path.copy())
else:
# For each neighbor of the current node, call the dfs function recursively
for neighbor in graph[node]:
dfs(neighbor, graph)
# Remove the current node from the path list (backtracking)
path.pop()
dfs(0, graph)
return result
```

## All Paths From Source To Target Solution Code

`1`