Coin Change II medium

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.

The order of coins doesn't matter.

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.

Steps

1. Dynamic Programming Approach: We'll use dynamic programming to solve this problem efficiently. We create a DP table dp of size amount + 1, where dp[i] represents the number of combinations to make up the amount i.

2. Initialization: We initialize dp[0] = 1, because there's one way to make up an amount of 0 (using no coins). All other elements of dp are initialized to 0.

3. Iteration: We iterate through the coins. For each coin c, we iterate through the DP table from c to amount. For each index i, we add dp[i - c] to dp[i]. This represents adding the coin c to the combinations that make up the amount i - c.

4. Result: After iterating through all coins, dp[amount] will contain the total number of combinations to make up the amount.

Explanation

The key idea is that for each coin, we can use it multiple times to make up the target amount. The DP table stores the number of ways to reach each amount. When considering a new coin, we add the number of ways to reach the current amount without that coin to the number of ways to reach the current amount with that coin. This avoids double-counting.

For example, if coins = [1, 2] and amount = 3, the DP table will evolve as follows:

• Initially: dp = [1, 0, 0, 0]
• After considering coin 1: dp = [1, 1, 1, 1] (1 way for each amount: all 1s)
• After considering coin 2: dp = [1, 1, 2, 3] (2 ways for amount 2: 2 or 1+1; 3 ways for amount 3: 2+1, 1+1+1, 3)

Code

#include <vector>

using namespace std;

int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1; // Base case: one way to make amount 0

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

    return dp[amount];
}

Complexity

• Time Complexity: O(amount * number of coins). The nested loops iterate through the DP table and coins.
• Space Complexity: O(amount). The DP table takes linear space with respect to the target amount.