0

I am writing a recursive DFS approach to find every path from 0 to (n-1) in a directed acyclic graph of n nodes given a list 'graph' where graph[i] is a list of all vertices that graph[i] can visit.

Here is my code:

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        
        end = len(graph)-1
        ans = []
        
        def dfs(path, node):
            if node == end:
                return path + [end]
            
            path = path + [node]

            for i in graph[node]:
                potentialAns = dfs(path, i)
                if potentialAns:
                    ans.append(potentialAns)
            
            return None
        
        dfs([], 0)
        return ans

where if I change path = path + [node] to path.append(node), behavior changes. For debugging purposes, given an input [[1,2],[3],[3],[]], after inserting print(path) before the for loop, using the former list extension method results in:

stdout: [0] [0, 1] [0, 1, 2] and a wrong answer of [[0,1,3],[0,1,2,3]]

Given the same input and print statement, using the latter list extension method results in:

stdout: [0] [0, 1] [0, 2] and the correct answer of [[0,1,3],[0,2,3]]

I am curious as to why this is; I believe that it may have something to with underlying behaviors of the two list extension methods.

Steven Zeng
  • 21
  • 2
  • One mutates the existing list, adding an element in-place. The other **creates a new list**. Observe – juanpa.arrivillaga Dec 19 '21 at 00:43
  • `path.append(node)` adds `node` as a single item. `path = path + [node]` adds each element of `node` as individual items. `list=list+[items]` is equivalent to `list.extend([items])` and is a different result. Play in the interactive interpreter and see for yourself – dawg Dec 19 '21 at 00:49
  • @dawg no, `path + [node]` doesn't work that way, and `list.extend([item])` is the same as `list.append(item)` – juanpa.arrivillaga Dec 19 '21 at 00:50
  • Note, the accepted answer in the linked duplicate links to the documentation for the `array` module, but it works the same for `list` objects and `array.array` objects – juanpa.arrivillaga Dec 19 '21 at 00:52
  • @juanpa.arrivillaga: Ahhm -- [read here](https://stackoverflow.com/a/28119966/298607) **Both + and += operators are defined for list. They are semantically similar to extend.** – dawg Dec 19 '21 at 14:37

0 Answers0