Path Sum II

Problem

Auditors trace approval chains from a root authority down to terminal signers, and a chain is compliant only when the accumulated weights along a full root-to-leaf path equal a mandated total. Given a binary tree and a target sum, return every root-to-leaf path whose node values sum to the target, in left-to-right leaf order.

Example 1:

Input: root = [9,6,14,3,8,11,17,null,null,null,null,null,12], targetSum = 18
Output: [[9, 6, 3]]
Explanation: the path 9 -> 6 -> 3 sums to 18; no other root-to-leaf path matches.

Example 2:

Input: root = [9,6,14,3,8,11,17,null,null,null,null,null,12], targetSum = 46
Output: [[9, 14, 11, 12]]
Explanation: the path 9 -> 14 -> 11 -> 12 is the only one reaching 46.

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

Tree:        9
           /   \
          6     14
         / \   /  \
        3   8 11  17
                \
                 12
 
paths and sums:
9-6-3   = 18  -> recorded at target 18
9-6-8   = 23
9-14-11-12 = 46  -> recorded at target 46
9-14-17 = 40

Solution Breakdown

Approach - DFS that threads the remaining sum and the live path downward, with an explicit pop on the way back.

Each call receives what the path still owes: remaining = target minus everything already on the path. It subtracts the current node's value, appends that value to a single shared path list, and recurses into both children. At a leaf - both children None - a residual of exactly zero means the values along this one root-to-leaf path summed to the target, so the path is recorded. The record must be a snapshot (path[:]), not the reference: path keeps mutating as the search moves on, and stored references would all alias the same list, corrupting the output.

The path.pop() after both recursive calls is the backtracking undo - the step that turns one shared list into an accurate window of the current chain. When a branch is exhausted, its values must leave the path so sibling branches build on the correct prefix; without the pop, values from dead branches accumulate and every recorded path would be polluted by leftovers. Unlike the boolean Path Sum, nothing short-circuits: or-style early exit would abandon unexplored paths that may match, so both subtrees are always visited, and results land in left-to-right leaf order. Trace target 18 on the example tree: the DFS descends 9 -> 6 -> 3, hits the leaf with residual 0, records [9, 6, 3]; the 8 leaf has residual 5, the 14 subtree residuals end at 28 and 22 - no other match.

Edge cases - an empty tree never reaches a leaf and returns []; a target nothing hits (100 on the example tree) leaves the accumulator empty; two branches producing equal paths (e.g. mirrored values both summing to the target) both appear in the output, since they are genuinely distinct root-to-leaf paths.

Complexity - O(n) visits with up to O(h) copy cost per matching leaf (O(n * h) worst case when every leaf matches on a balanced tree; O(n) when few do); O(h) auxiliary space for the recursion stack and the live path, O(n) worst case on a skewed tree, output excluded.