Path Sum II

We extend the Path Sum I approach to collect all valid paths instead of just checking existence. A mutable currentPath list is maintained. When we reach a valid leaf, a snapshot (copy) of currentPath is added to the result. The crucial backtracking step is removing the current node from currentPath before returning.

Algorithm:

• Add the current node's value to currentPath.
• Subtract the node's value from remaining.
• If a leaf is reached and remaining == 0, add a copy of currentPath to results.
• Recurse on left and right children.
• Backtrack: remove the last element from currentPath before returning.

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, targetSum, new ArrayList<>(), result);
    return result;
}

private void dfs(TreeNode node, int remaining,
                 List<Integer> currentPath,
                 List<List<Integer>> result) {
    if (node == null) return;

    currentPath.add(node.val);
    remaining -= node.val;

    if (node.left == null && node.right == null && remaining == 0) {
        result.add(new ArrayList<>(currentPath)); // snapshot copy
    }

    dfs(node.left,  remaining, currentPath, result);
    dfs(node.right, remaining, currentPath, result);

    // backtrack — remove current node before returning to parent
    currentPath.remove(currentPath.size() - 1);
}

• Time: O(n²). We visit every node O(n) times; copying a path at a leaf takes O(n) in the worst case (skewed tree). Overall O(n²) worst case.
• Space: O(n). currentPath holds at most h elements (tree height), plus O(h) recursion stack. Output list is not counted in auxiliary space.