Coin Change II – LeetCode Solution [Medium]


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.

LeetCode Problem Link


int: amount, int vector: coins[n]


an integer representing the number of combinations that make up that amount

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • 0 <= amount <= 5000
Sample Input
coins = [1,2,5], amount = 5
Sample Output

there are four ways to make up the amount:

This problem could be solved in polynomial time using Dynamic programming.

Dynamic Programming

This problem is similar to Coin Change problem, discussed here.

Optimal Substructure (Bottom up approach)

dp[j] represents the number of combinations that make up the amount j

Now according to optimal substructure:
for i = 0 to coins.size()-1:
  for j = coins[i] to amount:
    dp[j] = dp[j] + dp[j-coins[i]]

Base case & Initialisation

dp[0] = 1, number of ways to make sum = 0, is 1 (not including any coin)
dp[j] = 0, if j > 0
Code Implementation
    int change(int amount, vector<int>& coins) {
        int n = (int) coins.size();
        int dp[amount+1];
        dp[0] = 1;
        for(int i=1; i<=amount; i++) {
            dp[i] = 0;
        for(int i=0; i<n; i++) {
            for (int j=coins[i]; j<=amount; j++) {
                dp[j] += dp[j-coins[i]];

        return dp[amount];

Time complexity of the above solution is O(n*amount) (n is the size of coins vector) and auxiliary space required is O(amount).

Leave a Reply

Your email address will not be published. Required fields are marked *