_797. All Paths From Source to Target.md

797. All Paths From Source to Target

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : March 05, 2025

Last updated : March 05, 2025

---

Related Topics : Backtracking, Depth-First Search, Breadth-First Search, Graph

Acceptance Rate : 82.95 %

---

Since the edge is acyclic and directed, we do not have to worry about going back on our previous nodes

---

Solutions

• m797.py

Python

m797.py

class Solution:
    def _dfs_helper(self, curr: int, n: int, edges: defaultdict, path: List[int] = None, output: List[List[int]] = None) -> List[List[int]] :
        if output is None :
            output: List[List[int]] = []

        if path is None :
            path = [curr]

        if curr == n - 1 :
            output.append(path.copy())
            return

        for e in edges[curr] :
            path.append(e)
            self._dfs_helper(e, n, edges, path, output)
            path.pop()

        return output
        
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        return self._dfs_helper(0, len(graph), graph)