Daily LeetCode Problems: Problem 518. Coin Change II

Counting Coin Combinations: Solving the Coin Change II Problem

Introduction:

Welcome back to our daily LeetCode problem-solving series! Today, we’ll dive into problem 518, “Coin Change II.” In this problem, we are tasked with counting the number of combinations that can make up a given amount of money using coins of different denominations. We’ll walk through the problem statement, develop a strategic approach, provide step-by-step pseudocode, explain the underlying concepts, and analyze the complexity. Let’s dive in!

Problem Statement:

The problem presents us with an array coins representing coins of different denominations and an integer amount representing the total amount of money. Our goal is to find the number of combinations that can make up the given amount. If it's impossible to create the amount using the given coins, we need to return 0. It's important to note that we have an infinite supply of each coin denomination.

Approach:

To solve this problem, we can use dynamic programming. We’ll create an array dp, where dp[i] will represent the number of combinations to make the amount i. We'll iterate through the coin denominations for each amount and update the dp array accordingly.

Pseudocode:

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] += dp[i - coin]
        
        return dp[amount]

Explanation:

1. We initialize an array dp of size amount + 1 with all elements set to 0. dp[i] will store the number of combinations to make the amount i.
2. We set dp[0] to 1, as there's only one way to make the amount 0, which is by not using any coins.
3. For each coin denomination, we iterate through the dp array from coin to amount + 1.

• For each amount i, we add the number of combinations to make the amount i - coin to dp[i]. This is because adding a coin of denomination coin can contribute to forming the amount i.

1. Finally, we return dp[amount], which will contain the number of combinations to make the given amount.

Complexity Analysis:

• Time complexity: The nested loops iterate through each coin denomination for each amount from 1 to amount. Therefore, the time complexity is O(amount * n), where n is the number of coin denominations.
• Space complexity: We use an additional array dp of size amount + 1 to store the number of combinations for each amount. Thus, the space complexity is O(amount).

Full Solution

Python

class Solution:
  def change(self, amount: int, coins: List[int]) -> int:
    dp = [1] + [0] * amount

    for coin in coins:
      for i in range(coin, amount + 1):
        dp[i] += dp[i - coin]

    return dp[amount]

Java

class Solution {
  public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;

    for (final int coin : coins)
      for (int i = coin; i <= amount; ++i)
        dp[i] += dp[i - coin];

    return dp[amount];
  }
}

C++

class Solution {
 public:
  int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1);
    dp[0] = 1;

    for (const int coin : coins)
      for (int i = coin; i <= amount; ++i)
        dp[i] += dp[i - coin];

    return dp[amount];
  }
};

Conclusion:

In this article, we delved into the LeetCode problem 518, “Coin Change II.” We thoroughly understood the problem statement, devised a dynamic programming approach, provided pseudocode, explained the concept behind it, and analyzed its complexity. By utilizing dynamic programming techniques, we efficiently counted the number of combinations that can form a given amount using various coin denominations. Keep practising such problems to enhance your problem-solving skills. Stay tuned for more exciting LeetCode challenges in our daily series. Happy coding!