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 can be found at LeetCode 112. — Old Dog Programmer
– Old Dog Programmer, Commented Jun 11, 2023 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
– trincot, Commented Jun 11, 2023 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
– LaughTale, Commented Jun 11, 2023 at 19:17
Is that a follow up question? Either edit your question, or ask a new question. — trincot
– trincot, Commented Jun 11, 2023 at 19:43

Will Ness · Accepted Answer · 2023-06-12 00:47:03Z

0

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.

answered Jun 12, 2023 at 0:47

Will Ness

71.6k10 gold badges105 silver badges192 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Recursive approach with and without manual backtracking

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related