Path Sum II — find all root-to-leaf paths summing to target.

Problem. Given a binary tree and a target sum, return all root-to-leaf paths whose node values add up to the target. Each path is the list of node values from root to leaf.

The idea — DFS with backtracking

This is a textbook backtracking problem on a tree. Descend from the root, maintaining the current path and the remaining target. At a leaf, if the remaining target equals the leaf's value, the path is a hit — snapshot it. The crucial discipline: after exploring a node's children, remove it from the path so sibling branches start clean. That add-recurse-remove rhythm is the backtracking signature.

Optimal — O(n) traversal, output-bound, O(h) extra (excl. output)

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 n, int remaining,
                 List<Integer> path, List<List<Integer>> result) {
    if (n == null) return;

    path.add(n.val);                              // choose
    remaining -= n.val;

    if (n.left == null && n.right == null && remaining == 0) {
        result.add(new ArrayList<>(path));        // leaf + target hit -> snapshot a COPY
    } else {
        dfs(n.left,  remaining, path, result);    // explore
        dfs(n.right, remaining, path, result);
    }

    path.remove(path.size() - 1);                 // un-choose (backtrack)
}

Two details carry the correctness:

• Snapshot a copy (new ArrayList<>(path)) when recording a hit — path is mutated as we backtrack, so storing the reference would later corrupt it.
• The leaf test is both children null, not "remaining == 0 anywhere." The problem demands root-to-leaf paths; matching the sum mid-tree does not count.

We visit each node once, so the traversal is O(n), but copying matched paths can add up to O(n) per path; the total is bounded by the size of the output. The recursion stack and the working path are O(h).