LeetCode 所有路径题解

LeetCode 所有路径题解题目描述给定一个有向无环图找到所有从源节点到目标节点的路径。示例输入graph [[1,2],[3],[3],[]]输出[[0,1,3],[0,2,3]]解题思路方法回溯思路使用回溯算法遍历所有可能的路径。从源节点开始递归地探索所有邻居节点。当到达目标节点时将路径加入结果列表。复杂度分析时间复杂度O(V E)。空间复杂度O(V)。代码实现def all_paths_source_target(graph): result [] path [] def backtrack(node): path.append(node) if node len(graph) - 1: result.append(path[:]) else: for neighbor in graph[node]: backtrack(neighbor) path.pop() backtrack(0) return result # 测试 def test_all_paths_source_target(): graph [[1, 2], [3], [3], []] print(all_paths_source_target(graph)) # 输出[[0, 1, 3], [0, 2, 3]] if __name__ __main__: test_all_paths_source_target()总结所有路径是回溯的典型应用遍历所有从源节点到目标节点的路径。