Appending one list to another in recursion-CodePudding

So the question was to find all paths from source to target (

# code snippet 2

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        paths = []
        def dfsPath(node):
            if node == len(graph) - 1:
                print(validPath) # line 6
                paths.append(validPath.copy()) # line 7
                return paths
            else:
                for n in graph[node]:
                    validPath.append(n)
                    dfsPath(n)
                    validPath.pop()  
        validPath = [0]
        dfsPath(0)
        return paths

The only change in the above two code snippets is line 7. I've added the print statement in line 6 to show what validPath is holding. My question is why appending just validPath, results in a different output than when I append validPath.copy() (in line 7).

CodePudding user response：

list.copy() returns a shallow copy of the original list. It returns a new list, does not modify the original list.

so, when you did the pop() operation to backtrack on original list, the appended lists in the paths are also modified.

you may also use paths.append(validPath[:]) to get the whole sliced copy of the original list