algoadvance

Leetcode 518. Coin Change II

Problem Statement

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.

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

2. Input: amount = 3, coins = [2] Output: 0 Explanation: The amount of 3 cannot be made up just with coins of 2.

3. Input: amount = 10, coins = [10] Output: 1 Explanation: The amount of 10 can be made up only with a single coin of 10.

Clarifying Questions

1. Are the coin denominations and the amount guaranteed to be positive integers?
2. Is the function expected to handle both small and large inputs efficiently?
3. Are there any constraints on the number of coins or the value of amount?

Strategy

This problem is a variation of the classic “coin change problem.” We can solve this using dynamic programming (DP). The idea is to use a 1D DP array to keep track of the number of ways to get to each amount from 0 up to the target amount.

Here’s the step-by-step approach:

1. Initialize a DP array dp of size amount + 1 with all zeros except dp[0] which should be 1 because there is exactly one way to make the amount zero (using no coins).
2. For each coin, update the DP array from the coin value up to the target amount. The update rule is dp[i] += dp[i - coin], which means the number of ways to form amount i includes all the ways to form amount i - coin.

Code

Here’s the implementation in C++:

#include <vector>

int change(int amount, std::vector<int>& coins) {
    std::vector<int> dp(amount + 1, 0);
    dp[0] = 1; // Base case: One way to make amount 0
    
    for (const int &coin : coins) {
        for (int i = coin; i <= amount; ++i) {
            dp[i] += dp[i - coin];
        }
    }
    
    return dp[amount];
}

Time Complexity

• Time Complexity: (O(n \cdot m))
  • Where (n) is the amount and (m) is the number of coins.
  • We iterate over each coin and for each coin, we iterate through all sub-amounts up to amount.
• Space Complexity: (O(n))
  • We use a single array of size amount + 1 to keep track of the number of ways to make each amount.

This approach efficiently computes the number of possible combinations to make up the given amount using the provided coin denominations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?