JZX轻语：简

LeetCode 797 - 所有可能的路径

发表于2024年05月08日

#图论 #DFS #回溯法

回溯模板题，直接dfs回溯所有结果即可，由于是DAG，没必要维护一个visited数组。

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        n = len(graph)
        ans = []

        def traceback(cur_node: int, cur_path: List[int]):
            nonlocal graph, n

            if cur_node == n - 1:
                ans.append(list(cur_path))
                return

            for next_node in graph[cur_node]:
                cur_path.append(next_node)
                traceback(next_node, cur_path)
                cur_path.pop()

        traceback(0, [0])
        return ans

闪念标签：LC

题目链接：https://leetcode.cn/problems/all-paths-from-source-to-target/