When should we add return in the recursion

Question

Good day. May I have a question about when to use return in recursion. I basically want to use recursion to solve the below question:

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references. A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children. Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

Output: [[5,4,11,2],[5,8,4,5]]

Explanation: There are two paths whose sum equals targetSum:

5 + 4 + 11 + 2 = 22

5 + 8 + 4 + 5 = 22

Here is my code solution

def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        def helper(node, target, cur):
            if not node:
                return
            cur.append(node.val)
            if target == node.val and not node.left and not node.right:
                res.append(list(cur))
                print(res)
                return # why can't we put return here
            helper(node.left, target - node.val, cur)
            helper(node.right, target- node.val, cur)
            cur.pop()
        helper(root, targetSum, [])
        return res

I thought when we find one solution, we can stop and return the res. But it will give me a strange output. Could someone teach me why can't we put return here. Any suggestions would be appreciated.

Answer 1

This code uses the backtracking method to find all the solution (paths) to the problem.

When you return early, you deprive the solution of the opportunity to pop the last element that you added to your current list. Remove that early return and let the algorithm take care of returning at the base case, come back up the recursive stack and pop the last element from the current path, like follows:

def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        def helper(node, target, cur):
            if not node:
                return
            cur.append(node.val)
            if target == node.val and not node.left and not node.right:
                res.append(list(cur))
                print(res)
                # when your code comes out of this if condition
                # node.left and node.right will be None
                # it calls the below functions and they return
                # and then it will pop the last element
            helper(node.left, target - node.val, cur)
            helper(node.right, target- node.val, cur)
            cur.pop()
        helper(root, targetSum, [])
        return res