CODEWITHSUNDEEP
pythonrecursion
Arimee
Arimee

Reputation: 7

Appending one list to another in recursion

So the question was to find all paths from source to target (https://leetcode.com/problems/all-paths-from-source-to-target/).

# code snippet 1

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) # line 7
                return paths
            else:
                for n in graph[node]:
                    validPath.append(n)
                    dfsPath(n)
                    validPath.pop()  
        validPath = [0]
        dfsPath(0)
        return paths

enter image description here

# 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

enter image description here

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).

Upvotes: 0

Views: 54

Answers (1)

Abhishek Garg
Abhishek Garg

Reputation: 326

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

Upvotes: 1

Related Questions