Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Path Sum II
Bookmark
Path Copying
Backtracking
Iterative Stack
Input
Example 1
No Match
Single Path
Perfect Tree
Custom
tree
=
[5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]
,
targetSum
=
22
5
4
8
11
13
4
7
2
5
1
target = 22
path
paths
find every root-to-leaf path summing to
22
5
4
8
11
13
4
7
2
5
1
target = 22
path
paths
find every root-to-leaf path summing to
22
5
4
8
11
13
4
7
2
5
1
target = 22
remaining = 17
path
5
->
4
paths
visit
4
, still need 17
5
4
8
11
13
4
7
2
5
1
target = 22
remaining = 2
path
5
->
4
->
11
->
7
paths
leaf 7: remaining 2 != 7
, skip
5
4
8
11
13
4
7
2
5
1
target = 22
remaining = 2
path
5
->
4
->
11
->
2
paths
5→4→11→2
leaf 2: remaining 2 = value
-> copy path
5
4
8
11
13
4
7
2
5
1
target = 22
remaining = 2
path
5
paths
5→4→11→2
backtrack from
2
: drop it off the path
5
4
8
11
13
4
7
2
5
1
target = 22
remaining = 9
path
5
->
8
->
13
paths
5→4→11→2
leaf 13: remaining 9 != 13
, skip
5
4
8
11
13
4
7
2
5
1
target = 22
remaining = 5
path
5
->
8
->
4
->
5
paths
5→4→11→2
visit
5
, still need 5
5
4
8
11
13
4
7
2
5
1
target = 22
remaining = 5
path
5
->
8
->
4
->
1
paths
5→4→11→2
5→8→4→5
visit
1
, still need 5
5
4
8
11
13
4
7
2
5
1
target = 22
remaining = 5
path
5
paths
5→4→11→2
5→8→4→5
backtrack from
1
: drop it off the path
5
4
8
11
13
4
7
2
5
1
target = 22
path
paths
5→4→11→2
5→8→4→5
return [[5->4->11->2], [5->8->4->5]]
algo
master
.
io
Step:
Start: find every root-to-leaf path summing to 22
0 / 21
Input
Example 1
No Match
Single Path
Perfect Tree
Custom
tree
=
[5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]
,
targetSum
=
22
0 / 21
algo
master
.
io
Step:
Start: find every root-to-leaf path summing to 22
