educative.io

Educative

All-paths-for-a-sum- How's time complexity O(N^2)

How’s the time complexity for every leaf node to store its path which will take O(N)? We are just appending in the list, aren’t we?

Hi, I have the same question and hope the author can clear the confusion here

To store the path, we are making a copy of the current path, which will take O(N). Here is the relevant line for Java (here currentPath is a list):

allPaths.add(new ArrayList(currentPath));

For Python:

allPaths.append(list(currentPath))