回溯 - 递归调用中的列表更新问题

Question

我正在尝试解决 797。 Leetcode 从源到目标的所有路径 。我想到了将回溯与递归结合使用。在下面的代码中，当我从 path 中弹出时，列表 setOfPaths 也会更新。我不确定我在这里做错了什么。

class Solution(object):
    def allPathsSourceTarget(self, graph):
        path=[]
        setOfPaths=[]
        path.append(0)
        self.backtrack(graph,0,len(graph)-1,path,setOfPaths)
        return setOfPaths
    
    def backtrack(self,graph,src,dest,path,setOfPaths):
        if(src == dest):
            setOfPaths.append(path)
        else:
            for node in graph[src]:
                path.append(node)
                self.backtrack(graph,node,dest,path,setOfPaths)
                path.pop(len(path)-1)  #BackTracking

Answer 1

当您尝试将 path 附加到 setOfPaths 时，它并没有真正附加 path 的数据，而是对 path 或 [= 的引用11=] 附加变量本身。因为setOfPaths不包含数据，它包含变量，当你修改变量中的数据时，你会看到setOfPaths也被修改。

要摆脱它，最简单的方法是存储一个变量的副本，这样当您尝试修改“main”变量时就不会修改数据。

这段代码应该可以工作

if(src == dest):
    setOfPaths.append(path[:])

回溯 - 递归调用中的列表更新问题

Backtracking - problem with list updates in the recurrsive call

python

structure

backtracking

data-structures

recursive-backtracking