Coin Change II – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
You are given an integer array coins
representing coins of different denominations and an integer amount
representing a total amount of money.
Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0
.
You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.
Example 1:
Input: amount = 5, coins = [1,2,5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10] Output: 1
Constraints:
1 <= coins.length <= 300
1 <= coins[i] <= 5000
- All the values of
coins
are unique. 0 <= amount <= 5000
C++ Coin Change II LeetCode Solution
class Solution {
public:
int coinChange(vector<int>& coins, int n, int amount)
{
if(n==0)
return 0;
if(amount == 0)
{
return 1;
}
if(coins[n-1] > amount)
{
return coinChange(coins, n-1, amount);
}
return coinChange(coins, n, amount-coins[n-1]) + coinChange(coins, n-1, amount);
}
int change(int amount, vector<int>& coins) {
int n = coins.size();
if(amount == 0) {
return 1;
}
if(n==0)
return 0;
return coinChange(coins, n, amount);
}
};
Java Coin Change II LeetCode Solution
class Solution {
public int change(int amount, int[] coins) {
Integer[][] dp = new Integer[coins.length][amount + 1];
return dfs(coins, 0, amount, dp);
}
int dfs(int[] coins, int i, int amount, Integer[][] dp) {
if (amount == 0) return 1;
if (i == coins.length) return 0;
if (dp[i][amount] != null) return dp[i][amount];
int ans = dfs(coins, i + 1, amount, dp); // skip ith coin
if (amount >= coins[i])
ans += dfs(coins, i, amount - coins[i], dp); // use ith coin
return dp[i][amount] = ans;
}
}
Python 3 Coin Change II LeetCode Solution
class Solution(object):
def change(self, amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
#If we found a way to create the desired amount
if amount == 0:
return 1
#If we went over our amount or we have no more coins left
if amount < 0 or len(coins) == 0:
return 0
#Our solutions can be divided into two sets,
# 1) Solutions that cointain the coin at the end of the coins array
# 2) Solutions that don't contain that coin
return self.change(amount - coins[-1], coins) + self.change(amount, coins[:-1])
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1