Path Sum II
MediumThe same descent, recording every path
Problem
Return all root-to-leaf paths whose values sum to a target.
DFS carrying the path and remaining target; record the path whenever a leaf hits exactly zero.
The idea
Track the path as you go and copy it into the results whenever a leaf matches the target. Removing the node from the path as the recursion unwinds is what lets a single list serve every branch.
The trick
- Append, recurse, pop — the backtracking discipline.
- Copy the path when recording it, or every result aliases the same list.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [5,4,8,11,...], target=22 Values: 5, 4, 8, 11, 22.
1dfs(node, rem, path):2 path.push(node.val); rem-=node.val3 if leaf and rem==0: output path4 else dfs(children)5 path.pop()Input
- array
- [5, 4, 8, 11, 22]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [5,4,8,11,null,13,4,7,2,null,null,5,1], target = 22
- Output:
- [[5, 4, 11, 2], [5, 8, 4, 5]]
- Explanation:
- All root-to-leaf paths summing to 22.
Example 2
- Input:
- tree = [1,2,3], target = 3
- Output:
- [[1, 2]]
- Explanation:
- Only 1→2 makes 3.
Example 3
- Input:
- tree = [1,2], target = 0
- Output:
- []
- Explanation:
- No path sums to 0 → none.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.