Sum of paths III - Leetcode

Question

Given a target sum , we need to find the path count i.e total no of paths. Also it is given that , it is not necessary the path needs to start from the root node.

I came across a solution , for this question. I am also able to understand 85% of the solution.

Solution :

def pathCounter(node,currPath,_sum):
    if node is None:
        return 0
    path = []
    currPath.append(node.data)
    
    pathSum , pathCount = 0, 0
      
    #Unable to understand below for loop
    for i in range(len(currPath)-1,-1,-1):
        
        pathSum +=currPath[i]
        path.append(currPath[i])
        
        
        if pathSum==_sum:
            pathCount+=1
            #print(path)
            
    pathCount+= pathCounter(node.left,currPath,_sum)
    pathCount+= pathCounter(node.right,currPath,_sum)
    
    del currPath[-1]
    
    
    return pathCount

The issue I have is, I am unable to understand , why the for loop is set to iterate in reverse order and not in normal order ?

How does this affect the problem ?

I will be returning only the pathCount, commenting the path won't be an issue — Ragesh Kr
– Ragesh Kr, Commented Jun 14, 2021 at 9:18
I used it for debugging purpose. Also wanted to check if I can print the path. — Ragesh Kr
– Ragesh Kr, Commented Jun 14, 2021 at 14:21
Nope, if I replace the line of code with '"for i in range(len(currPath)): " it does not work — Ragesh Kr
– Ragesh Kr, Commented Jun 18, 2021 at 4:49
You're right. But the order of the accumulating sum is important. I posted an answer. — trincot
– trincot, Commented Jun 18, 2021 at 8:35

trincot · Accepted Answer · 2021-06-18 08:34:42Z

The reason is that when you perform the loop in the forward direction, the if condition is going to check the sums that represent a prefix of currPath, instead of a postfix.

As the recursion appends node values at the end of currPath it does not make sense to repeat the check of prefix sums (as that would already have been checked earlier on). The prefix sums would always include (the value of) the root node, while we cannot assume the root node must be included in a solution.

The purpose of the recursion is to include the newly visited node in all sum-checks, and since that new node is sitting at the end of currPath, the sum should accumulate from the end in a backwards direction.

For example:

Let's say there is a downward path in the tree with these values: 10 - 5 - 3 - 1, and that we need to find a sum of 8. Then in the first level of recursion, we visit 10, and in the next we visit 5. At this point we verify these sums:

* 5
* 5 + 10

Neither gives a match, so we recur deeper and visit 3. Now we check these sums:

* 3
* 3 + 5 => It's a match!
* 3 + 5 + 10

If at this stage we would have done a forward loop, we would have checked these sums:

* 10
* 10 + 5
* 10 + 5 + 3

None would match, and we would never have checked any sum that does not include the root.

Collectives™ on Stack Overflow

Sum of paths III - Leetcode

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related