304 North Cardinal St.
Dorchester Center, MA 02124

# Coin Change LeetCode Solution

## Problem – Coin Change

You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return `-1`.

You may assume that you have an infinite number of each kind of coin.

Example 1:

``````Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
``````

Example 2:

``````Input: coins = [2], amount = 3
Output: -1``````

Example 3:

``````Input: coins = [1], amount = 0
Output: 0``````

Constraints:

• `1 <= coins.length <= 12`
• `1 <= coins[i] <= 231 - 1`
• `0 <= amount <= 104`

### Coin Change LeetCode Solution in C++

``````class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int Max = amount + 1;
vector<int> dp(amount + 1, Max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.size(); j++) {
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
``````

### Coin Change LeetCode Solution in Java

``````public class Solution {
public int coinChange(int[] coins, int amount) {
if(amount<1) return 0;
return helper(coins, amount, new int[amount]);
}

private int helper(int[] coins, int rem, int[] count) { // rem: remaining coins after the last step; count[rem]: minimum number of coins to sum up to rem
if(rem<0) return -1; // not valid
if(rem==0) return 0; // completed
if(count[rem-1] != 0) return count[rem-1]; // already computed, so reuse
int min = Integer.MAX_VALUE;
for(int coin : coins) {
int res = helper(coins, rem-coin, count);
if(res>=0 && res < min)
min = 1+res;
}
count[rem-1] = (min==Integer.MAX_VALUE) ? -1 : min;
return count[rem-1];
}
}
``````

### Coin Change LeetCode Solution in Python

``````class Solution(object):
def coinChange(self, coins, amount):
MAX = float('inf')
dp = [0] + [MAX] * amount

for i in xrange(1, amount + 1):
dp[i] = min([dp[i - c] if i - c >= 0 else MAX for c in coins]) + 1

return [dp[amount], -1][dp[amount] == MAX]
``````
##### Coin Change LeetCode Solution Review:

In our experience, we suggest you solve this Coin Change LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Coin Change LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Coin Change LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions