Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Coin Change II
Bookmark
Memoization
Bottom-Up 2D
Bottom-Up 1D
Input
Example 1
Example 2 (odd)
Example 3 (exact)
Example 4
Example 5
Custom
amount
=
5
,
coins
=
[1, 2, 5]
coins (index, remaining)
1
2
5
coins (index, remaining)
1
2
5
coins (index, remaining)
1
2
5
0,5
1,5
2,5
3,5
0
2,0
1,3
2,3
3,3
2,-2
1,1
2,1
3,1
2,-4
1,-1
0,4
1,4
2,4
3,4
2,-1
1,2
2,2
3,2
2,-3
1,0
0,3
1,3
0,2
1,2
0,1
1,1
0,0
out of coins: 0 ways
coins (index, remaining)
1
2
5
0,5
1,5
2,5
1
3,5
0
2,0
1
1,3
2,3
3,3
0
2,-2
1,1
2,1
3,1
2,-4
1,-1
0,4
1,4
2,4
3,4
2,-1
1,2
2,2
3,2
2,-3
1,0
0,3
1,3
0,2
1,2
0,1
1,1
0,0
out of coins: 0 ways
memo
(2,5)=1
coins (index, remaining)
1
2
5
0,5
1,5
2,5
1
3,5
0
2,0
1
1,3
2,3
0
3,3
0
2,-2
0
1,1
2,1
3,1
2,-4
1,-1
0,4
1,4
2,4
3,4
2,-1
1,2
2,2
3,2
2,-3
1,0
0,3
1,3
0,2
1,2
0,1
1,1
0,0
count(3, 1)
memo
(2,5)=1
(2,3)=0
coins (index, remaining)
1
2
5
0,5
1,5
1
2,5
1
3,5
0
2,0
1
1,3
0
2,3
0
3,3
0
2,-2
0
1,1
0
2,1
0
3,1
0
2,-4
0
1,-1
0
0,4
1,4
2,4
3,4
2,-1
1,2
2,2
3,2
2,-3
1,0
0,3
1,3
0,2
1,2
0,1
1,1
0,0
memo[(1,5)] = 1 + 0 = 1
memo
(2,5)=1
(2,3)=0
(2,1)=0
(1,1)=0
(1,3)=0
(1,5)=1
coins (index, remaining)
1
2
5
0,5
1,5
1
2,5
1
3,5
0
2,0
1
1,3
0
2,3
0
3,3
0
2,-2
0
1,1
0
2,1
0
3,1
0
2,-4
0
1,-1
0
0,4
1,4
2,4
3,4
0
2,-1
1,2
2,2
3,2
2,-3
1,0
0,3
1,3
0,2
1,2
0,1
1,1
0,0
count(2, -1)
memo
(2,5)=1
(2,3)=0
(2,1)=0
(1,1)=0
(1,3)=0
(1,5)=1
coins (index, remaining)
1
2
5
0,5
1,5
1
2,5
1
3,5
0
2,0
1
1,3
0
2,3
0
3,3
0
2,-2
0
1,1
0
2,1
0
3,1
0
2,-4
0
1,-1
0
0,4
1,4
2,4
0
3,4
0
2,-1
0
1,2
2,2
3,2
0
2,-3
1,0
0,3
1,3
0,2
1,2
0,1
1,1
0,0
count(2, -3)
memo
(2,5)=1
(2,3)=0
(2,1)=0
(1,1)=0
(1,3)=0
(1,5)=1
(2,4)=0
coins (index, remaining)
1
2
5
0,5
1,5
1
2,5
1
3,5
0
2,0
1
1,3
0
2,3
0
3,3
0
2,-2
0
1,1
0
2,1
0
3,1
0
2,-4
0
1,-1
0
0,4
1,4
1
2,4
0
3,4
0
2,-1
0
1,2
1
2,2
0
3,2
0
2,-3
0
1,0
1
0,3
1,3
0,2
1,2
0,1
1,1
0,0
skip coin 1 or use it once
memo
(2,5)=1
(2,3)=0
(2,1)=0
(1,1)=0
(1,3)=0
(1,5)=1
(2,4)=0
(2,2)=0
(1,2)=1
(1,4)=1
coins (index, remaining)
1
2
5
0,5
1,5
1
2,5
1
3,5
0
2,0
1
1,3
0
2,3
0
3,3
0
2,-2
0
1,1
0
2,1
0
3,1
0
2,-4
0
1,-1
0
0,4
1,4
1
2,4
0
3,4
0
2,-1
0
1,2
1
2,2
0
3,2
0
2,-3
0
1,0
1
0,3
1,3
0
0,2
1,2
1
0,1
1,1
0,0
count(1, 1)
memo
(2,5)=1
(2,3)=0
(2,1)=0
(1,1)=0
(1,3)=0
(1,5)=1
(2,4)=0
(2,2)=0
(1,2)=1
(1,4)=1
coins (index, remaining)
1
2
5
0,5
4
1,5
1
2,5
1
3,5
0
2,0
1
1,3
0
2,3
0
3,3
0
2,-2
0
1,1
0
2,1
0
3,1
0
2,-4
0
1,-1
0
0,4
3
1,4
1
2,4
0
3,4
0
2,-1
0
1,2
1
2,2
0
3,2
0
2,-3
0
1,0
1
0,3
2
1,3
0
0,2
2
1,2
1
0,1
1
1,1
0
0,0
1
4 combinations make 5
memo
(2,5)=1
(2,3)=0
(2,1)=0
(1,1)=0
(1,3)=0
(1,5)=1
(2,4)=0
(2,2)=0
(1,2)=1
(1,4)=1
(0,1)=1
(0,2)=2
(0,3)=2
(0,4)=3
(0,5)=4
algo
master
.
io
Step:
Coins 1, 2, 5 and an amount of 5. Count the combinations that make it.
0 / 79
Input
Example 1
Example 2 (odd)
Example 3 (exact)
Example 4
Example 5
Custom
amount
=
5
,
coins
=
[1, 2, 5]
0 / 79
algo
master
.
io
Step:
Coins 1, 2, 5 and an amount of 5. Count the combinations that make it.
