Hi, why do we need this step: del currentPath[-1]?
Thanks
Type your question above this line.
Hi @Yuchuan_Han
It is important to note that during the whole process of counting paths for a sum S, there is only one currentPath list. It is the one that is created in the initial call:
count_paths_recursive(root, S, [])
# ^---here!
All that happens to that single list is that elements are appended to it, and then deleted from it again (when backtracking). It continually grows and shrinks, grows and shrinks,… throughout its lifetime. But it is the same, single list instance.
That’s why it is important to del (delete) the values from the list when backtracking.
Hi @Yuchuan_Han,
Exactly what @Usman_Younas said.
However I would like to clarify a bit as I understand where the confusion might be coming from.
You might be thinking that you passed a list to each child node like the example:
pathCount += count_paths_recursive(currentNode.left, S, currentPath)
pathCount += count_paths_recursive(currentNode.right, S, currentPath)
and at that time the correct number of nodes were in that list so why should we care about what we might have added further down the list?
The answer lies more to how lists in python and other languages work rather than the solution.
Lists in python are what we call reference types meaning what your variable in this case currentPath holds is a memory address to the beginning of your list and not the actual list.
Say for an example sake:
currentPath = [1, 2, 3, 4]
Even if you did:
new_path = currentPath and added a value inside new_path like:
new_path.append(10) this would now reflect in currentPath as well.
So print(currentPath) would return [1, 2, 3, 4, 10]
I hope this explanation helps and feel free to see another post of mine where I explain this there as well