Backtracking - problem with list updates in the recurrsive call

Question

I was trying to solve 797. All Paths From Source to Target from Leetcode. I thought of using Backtracking with recursion. In the below code, the list setOfPaths is also getting updated when I pop from path. I am not sure what I am doing wrong here.

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

When you try to append path to the setOfPaths, it do not really append the path's data, but the reference to path or path variable itself is appended. Because setOfPaths did not contain the data, it contained the variable, when you modified data inside variable, you would see setOfPaths also be modified.

To get rid of it, the simplest way is to store a copy of variable, so that you would not modified the data when you try to modify the "main" variable.

This piece of code should work

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