LeetCode DAG所有路径题Python回溯代码错误排查

• 题目：LeetCode 所有可能的路径
• 题目要求：给定节点编号为0到n-1的有向无环图（DAG），查找所有从节点0到节点n-1的路径，返回结果顺序不限。图的表示规则为：graph[i]存储所有从节点i出发可直接到达的节点，即存在i指向graph[i][j]的有向边。
• 测试用例输入：

[[1,2],[3],[3],[]]

• 预期输出：

[[0,1,3],[0,2,3]]

问题代码 #

class Solution:
    def allPathsSourceTargetUtil(self, n, graph, visited, ans):
        visited.append(n)
        
        if n == len(graph)-1:
            ans.append(visited)
            print(ans)
        else:
            for i in graph[n]:
                self.allPathsSourceTargetUtil(i, graph, visited, ans)
            
                visited.pop()
        
        
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        ans  = []
        visited = []
        n = 0
        
        self.allPathsSourceTargetUtil(n, graph, visited, ans)
        
        return ans

异常表现 #

运行上述测试用例时，中间打印结果为：

[[0, 1, 3]]
[[0, 2, 3], [0, 2, 3]]

最终返回结果为[[0],[0]]，与预期输出不符。

逻辑错误定位 #

代码存在两处核心问题：

1. 列表引用传递错误：ans.append(visited)存入结果列表的是visited的内存引用，不是当前路径的独立副本。后续回溯过程中对visited的append、pop修改会同步改动所有已经存入ans的路径内容，最终所有存储的路径都会指向回溯完成后的最终visited状态。
2. 回溯pop位置错误：当前visited.pop()写在else分支的for循环内部，当递归走到终点（节点n-1）时，不会执行pop操作，回溯状态回退链路断裂，路径状态无法正确还原。

修复后代码 #

from typing import List

class Solution:
    def allPathsSourceTargetUtil(self, n, graph, visited, ans):
        visited.append(n)
        if n == len(graph) - 1:
            # 存储当前路径的独立副本
            ans.append(visited.copy())
        else:
            for i in graph[n]:
                self.allPathsSourceTargetUtil(i, graph, visited, ans)
        # 统一执行回溯回退，无论当前是否为终点，递归返回后都要弹出当前节点
        visited.pop()
    
    
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        ans = []
        visited = []
        self.allPathsSourceTargetUtil(0, graph, visited, ans)
        return ans

运行修复后的代码，传入测试用例可得到正确输出[[0,1,3],[0,2,3]]。

内容的提问来源于stack exchange，提问作者Suman Kumar