Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Path Sum II

LeetCode #113Medium
Backtracking: collect every root-to-leaf path == target

Given the root of a binary tree and a target sum, return all root-to-leaf paths whose node values add up exactly to the target.

Asked atAmazonMeta
step 1 / 36
binary tree
7
11
2
4
5
13
8
5
4
1
call stack ↓
(returned)
Recursive DFS + backtracking
▸
1dfs(node, remaining):
2    path.push(node.val); remaining -= node.val   // go down
3    if leaf and remaining == 0: results.push(copy of path)
4    dfs(node.left,  remaining)
5    dfs(node.right, remaining)
6    path.pop()                                    // backtrack
7// answer = results
state
  • target22
  • path[]
  • results∅

line 1Path Sum II asks for EVERY root-to-leaf path whose values sum to 22. One path isn't enough, so we can't short-circuit — we must explore the whole tree. The technique is BACKTRACKING: push a node onto the current path on the way DOWN, and POP it on the way back UP, so the path always reflects exactly where we are.