0

This is a code for DFS all paths from source to the destination where source = 0 and destination = size of the graph - 1. In Line 12, why can't I simply do res.append((path)) since the path is already a list?

from collections import defaultdict
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        adjlist = defaultdict(list)
        for i in range(len(graph)):
            adjlist[i].extend(graph[i])
        start = 0
        destination = len(graph) -  1
        res = []
        def dfs(node,path):
            nonlocal res
            if node == destination:
                res.append(list(path))
                return 
            if node in adjlist:
                for nextNode in adjlist[node]:
                    path.append(nextNode)
                    dfs(nextNode,path)
                    path.pop()
        dfs(0,[0])
        print(res)
ggorlen
  • 44,755
  • 7
  • 76
  • 106
Ajinkya Ghadge
  • 103
  • 1
  • 1
  • 6
  • 1
    If you `return res`, this passes [leetcode](https://leetcode.com/problems/all-paths-from-source-to-target). `list(path)` makes a shallow copy of the `path` object, otherwise you're just appending an alias of the same list over and over again and winding up with corrupt results. – ggorlen Feb 11 '21 at 18:45

1 Answers1

1

When you simply pass the path, it passes a reference to the path variable. Essentially, you would be referring to the original path variable.

list(path) would essentially append a shallow copy of the path as a new list, hence changes made to the path will not be reflected.

Saisha
  • 94
  • 5