发表于 2024.05.08

• 回溯模板题，直接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 题目链接