113 · Path Sum II

LC 112 and LC 257 composed, plus one new rule: copy on record. Write new ArrayList<>(path), or every result aliases the same list and you return N copies of an empty one.

1 — The problem

Return all root-to-leaf paths summing to the target, as lists of values. Three pieces, each already solved:

One structural difference from 112 is easy to miss: there is no short-circuit. 112 stops at the first success because it only needs to know whether a path exists; 113 needs all of them, so both children are always visited and the method returns void.

2 — Every path, not the first

Target 22, and two paths qualify: 5→4→11→2 and 5→8→4→5. Watch the second one get found — 112 would have returned before ever entering node 8.

The output strip holds finished snapshots while the path strip keeps churning. Those are different objects, and keeping them different is the point of line 5.

2.1 What happens without the copy

Write out.add(path) and the code still compiles, still finds both leaves, and still adds two elements to out. Both of them are the same object — the one live path list — and by the time the traversal ends, line 8 has emptied it:

The failure is spectacular rather than subtle, which is the good news. The related bug in LC 437 — forgetting to undo a shared hash map — produces plausible wrong numbers instead, and is much harder to spot.

2.2 Where the leaf test sits

Line 4 is a three-way conjunction, and the order matters for readability but not correctness: both children null and the value finishes the target. Splitting it into a nested if is fine. What is not fine is recording when only the sum matches:

• nd.val == rem alone fires at internal nodes, emitting prefixes that are not root-to-leaf paths.
• On a tree containing a 0 further down, a prefix can match the target and the true path continue past it — so this bug both adds wrong answers and keeps the right ones, which makes the output look almost correct.

3 — Complexity and edge cases

• Time O(n · h) — O(n) to walk, and each recorded path costs O(h) to copy. In the worst case (a perfect tree where every path matches) the output alone is Θ(n log n).
• Space O(h) for the recursion and live path, plus the output.
• No match: an empty list, not null.
• Empty tree: empty list, for any target including 0.
• Negative values: supported, and again they forbid pruning on rem < 0.
• Common bug: out.add(path) without the copy.
• Common bug: returning early after a match, skipping line 8. The leaf never pops itself and the next path inherits it — the same trap as LC 257, now with silently corrupted output rather than an obviously wrong string.

4 — Reference implementation

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

private void dfs(TreeNode nd, int rem,
                 List<Integer> path, List<List<Integer>> out) {
    if (nd == null) return;
    path.add(nd.val);
    if (nd.left == null && nd.right == null && nd.val == rem)
        out.add(new ArrayList<>(path));      // snapshot, not the live list
    dfs(nd.left,  rem - nd.val, path, out);
    dfs(nd.right, rem - nd.val, path, out);   // no short-circuit — collect all
    path.remove(path.size() - 1);
}