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. Initialization: Create a DP table dp of size amount + 1, initialized with 0. dp[i] will store the number of combinations to make up amount i. We initialize dp[0] = 1 because there's one way to make an amount of 0 (using no coins).

2. Iteration: Iterate through each coin denomination coin in coins.

3. Inner Iteration: For each coin, iterate through the DP table from the coin value up to the amount.

4. DP Update: For each index i in the inner loop, update dp[i] by adding dp[i - coin]. This represents adding the current coin to the existing combinations that made up the amount i - coin.

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

Explanation

This problem uses dynamic programming. The key idea is to build up the solution iteratively. dp[i] represents the number of ways to make up amount i. When considering a new coin, we add the number of ways to make up i - coin to the existing number of ways to make up i. This is because adding the current coin to combinations that sum to i - coin creates new combinations that sum to i.

Code

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        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 the coins.
• Space Complexity: O(amount). The DP table dp uses space proportional to the amount.