Recursive approach with and without manual backtracking

Question

In some cases, like the "hasPathSum" problem, where we are checking for a specific condition (e.g., targetSum == 0) at leaf nodes, we don't need manual backtracking. The recursion naturally backtracks as it reaches the leaf nodes, and the state is automatically maintained correctly.

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null 
                              && targetSum == root.val) 
             return true;
        return hasPathSum(root.left, targetSum - root.val) 
                || hasPathSum(root.right, targetSum - root.val);
    }
}

Same problem,In such cases, we need to manually backtrack to the previous state when moving back up the recursive calls.

class Solution {
    int count = 0;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        dfs(root, targetSum);
        return count;
    }

    public void dfs(TreeNode node, int targetSum) {
        if (node == null) return;

        targetSum -= node.val;
        if (targetSum == 0) {
            count++;
        }

        dfs(node.left, targetSum);
        dfs(node.right, targetSum);

        targetSum += node.val; // Backtrack, restore the previous state
    }
}

I don't understand how the values of parameters are passed in recursion, and why manual backtracking is needed when using the targetSum variable. Please help.

A [description of the "path sum" problem](https://leetcode.com/problems/path-sum/) can be found at LeetCode 112. — Old Dog Programmer, Jun 11 '23 at 18:22
There is no need to update `targetSum` at the end -- it is at its end-of-life: no-one cares anymore what its value is. What you call "manual" backtracking is not needed in the second case either. — trincot, Jun 11 '23 at 18:51
1.if (node.right != null) { if (traversal(node.right, count - node.right.val) return true; } 2.if (node.right != null) { count -= count.right.val; if (traversal(node.right, count)) return true; count += count.right.val } how about these? — LaughTale, Jun 11 '23 at 19:17
Is that a follow up question? Either edit your question, or ask a new question. — trincot, Jun 11 '23 at 19:43
regarding arguments, see e.g. [this](https://stackoverflow.com/a/76009361/849891) or [this](https://stackoverflow.com/a/46613542/849891). — Will Ness, Jun 12 '23 at 00:57

score 0 · Answer 1 · answered Jun 12 '23 at 00:47

You need to manually undo any changes that you make to some external, global variable's value, before making the next attempt's change to the same value, because it is the same entity used by all calls.

One example is backtracking search for e.g. Sudoku solution, maintaining one global 9x9 matrix. Another is producing all permutations of elements of a list. Yet another might be 8 Queens problem in chess, with 8x8 board.

If you pass that value's copy to each recursive invocation as one of its arguments, then the previous one remains unchanged and you need no manual undoing. But it can result in heavier memory usage, naturally.

Recursive approach with and without manual backtracking

1 Answers1