Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Path Sum III
Bookmark
Brute Force
Prefix Sum + Map
Input
Example 1
Example 2
Simple Tree
Custom
tree
=
[10, 5, -3, 3, 2, null, 11, 3, -2, null, 1]
,
targetSum
=
8
10
5
-3
3
2
11
3
-2
1
target = 8
count = 0
paths
count downward paths summing to
8
10
5
-3
3
2
11
3
-2
1
target = 8
count = 0
paths
count downward paths summing to
8
10
start
5
-3
3
Σ=18
2
11
3
-2
1
target = 8
count = 0
paths
from 10: sum =
18
!= 8
10
start
5
-3
3
2
11
3
-2
1
Σ=18
target = 8
count = 0
paths
from 10: sum =
18
!= 8
10
5
Σ=5
-3
3
2
11
3
-2
1
target = 8
count = 0
paths
from 5: sum =
5
!= 8
10
5
start
-3
3
2
Σ=7
11
3
-2
1
target = 8
count = 1
paths
5→3
from 5: sum =
7
!= 8
10
5
-3
3
start
2
11
3
Σ=6
-2
1
target = 8
count = 2
paths
5→3
5→2→1
from 3: sum =
6
!= 8
10
5
-3
3
2
11
3
-2
start
1
target = 8
count = 2
paths
5→3
5→2→1
new start
-2
: search every path downward
10
5
-3
3
2
start
11
3
-2
1
Σ=3
target = 8
count = 2
paths
5→3
5→2→1
from 2: sum =
3
!= 8
10
5
-3
Σ=-3
3
2
11
3
-2
1
target = 8
count = 2
paths
5→3
5→2→1
from -3: sum =
-3
!= 8
10
5
-3
3
2
11
3
-2
1
target = 8
count = 3
paths
5→3
5→2→1
-3→11
return 3
algo
master
.
io
Step:
Start: count every downward path that sums to 8
0 / 36
Input
Example 1
Example 2
Simple Tree
Custom
tree
=
[10, 5, -3, 3, 2, null, 11, 3, -2, null, 1]
,
targetSum
=
8
0 / 36
algo
master
.
io
Step:
Start: count every downward path that sums to 8
