Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Coin Change II
Bookmark
O(n × amount) Space
O(amount) Space
Input
Example 1
Example 2 (odd)
Example 3 (exact)
Example 4
Example 5
Custom
amount
=
5
,
coins
=
[1, 2, 5]
coins
1
2
5
amount =
5
amount j
0
1
2
3
4
5
coins used
-
+1
+2
+5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
how many coin combinations make 5? order does not matter
coins
1
2
5
amount =
5
amount j
0
1
2
3
4
5
coins used
-
+1
+2
+5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
how many coin combinations make 5? order does not matter
coins
1
2
5
amount =
5
coin
amount j
0
1
2
3
4
5
coins used
-
+1
+2
+5
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
coin = 1
row 1: combinations may now use it
coins
1
2
5
amount =
5
coin
amount j
0
1
2
3
4
5
coins used
-
+1
+2
+5
1
0
0
0
0
0
1
1
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
+1
dp[1][2]
=
0
+ dp[1][
1
] =
0
+
1
=
1
coins
1
2
5
amount =
5
coin
amount j
0
1
2
3
4
5
coins used
-
+1
+2
+5
1
0
0
0
0
0
1
1
1
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
dp[1][4]
= dp[
0
][4] =
0
without the new coin
coins
1
2
5
amount =
5
coin
amount j
0
1
2
3
4
5
coins used
-
+1
+2
+5
1
0
0
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
coin = 2
row 2: combinations may now use it
coins
1
2
5
amount =
5
coin
amount j
0
1
2
3
4
5
coins used
-
+1
+2
+5
1
0
0
0
0
0
1
1
1
1
1
1
1
1
2
0
0
0
1
0
0
0
0
0
+1
dp[2][2]
=
1
+ dp[2][
0
] =
1
+
1
=
2
coins
1
2
5
amount =
5
coin
amount j
0
1
2
3
4
5
coins used
-
+1
+2
+5
1
0
0
0
0
0
1
1
1
1
1
1
1
1
2
2
3
0
1
0
0
0
0
0
+2
dp[2][4]
=
1
+ dp[2][
2
] =
1
+
2
=
3
coins
1
2
5
amount =
5
coin
amount j
0
1
2
3
4
5
coins used
-
+1
+2
+5
1
0
0
0
0
0
1
1
1
1
1
1
1
1
2
2
3
3
1
0
0
0
0
0
coin = 5
row 3: combinations may now use it
coins
1
2
5
amount =
5
coin
amount j
0
1
2
3
4
5
coins used
-
+1
+2
+5
1
0
0
0
0
0
1
1
1
1
1
1
1
1
2
2
3
3
1
1
2
2
3
0
3
dp[3][4]
= dp[
2
][4] =
3
coin 5 > 4, copy only
coins
1
2
5
amount =
5
amount j
0
1
2
3
4
5
coins used
-
+1
+2
+5
1
0
0
0
0
0
1
1
1
1
1
1
1
1
2
2
3
3
1
1
2
2
3
4
4
combinations make 5
algo
master
.
io
Step:
How many combinations of coins make 5?
0 / 31
Input
Example 1
Example 2 (odd)
Example 3 (exact)
Example 4
Example 5
Custom
amount
=
5
,
coins
=
[1, 2, 5]
0 / 31
algo
master
.
io
Step:
How many combinations of coins make 5?
