Nested list in python returns empty list during DFS recursion

Question

I am having a graph dict using defaultdict representing the adjacency list of graph in python3 and want to perform a DFS over this graph. Now, problem is to find all routes from a starting word beginWord and reach endWord, and I am applying DFS for that recursion + backtracking.

ex.

beginWord = "hit"   
endWord = "cog"   
graph : defaultdict(<class 'list'>, {'hit': ['hot'], 'hot': ['dot', 'lot'], 'dot': ['dog'], 'lot': ['log'], 'dog': ['cog'], 'log': ['cog']})

Output should be like :

[["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]]

My approach :
I am having my graph already made and created two new list : path[] and ans[].
path basically goes on starting from beginWord till it reaches endWord and when it does, I append it to ans variable (now it is a 2-d nested list), then pop the last word from the list to trigger backtracking. I will continue doing this until all the paths are explored and stored in ans[] list.

problem :
ans[] returns empty list but it contains two nested empty lists which indicates it knows that answer is two lists which is true but why did it popped that items ?

My code :

def DFS(beginWord, endWord, graph, path, ans):

    path.append(beginWord)
    if beginWord == endWord:
        ans.append(path)
        path.pop()
        return

    for i in graph[beginWord]:
        DFS(i, endWord, graph, path, ans)

    path.pop()

Note : using extend instead of append for ans[] works (not exactly but I get the path) but why not append ?

Answer 1

You have a single list path. When you modify this list, you modify it everywhere it occurs, including the places that you pushed it onto ans.

Instead, you need something like ans.append(path.copy()) which copies the path before appending it to the answer. Any subsequent changes you make to path will not affect what you have already pushed onto ans.