All Paths From Source To Target - Leetcode Solution

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:

1. Create an empty list called 'result' to store all possible paths.
2. Create an empty list called 'path' to store the current path.
3. Define a recursive function called 'dfs' with input parameters as the current node and the graph.
4. 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).
5. Call the 'dfs' function with the initial node as 0.
6. 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

1