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 (Dynamic Programming) array dp of size amount + 1. Initialize dp[0] to 1 (there's one way to make amount 0: using no coins). The rest of the elements are initialized to 0.

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

3. Inner Iteration: For each coin, iterate through the dp array from the coin's value up to amount.

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

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

Explanation

This problem uses dynamic programming to efficiently count the combinations. The dp array stores the number of ways to make up each amount from 0 to amount. The outer loop iterates through each coin denomination. The inner loop iterates through possible amounts, adding the number of ways to make up the smaller amount (i - coin) to the number of ways to make up the current amount (i). This cleverly accounts for all possible combinations. The base case dp[0] = 1 is crucial because it represents the single way to make up an amount of 0 (using no coins).

Code

public 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

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

        return dp[amount];
    }
}

Complexity

• Time Complexity: O(amount * n), where n is the number of coins. This is because of the nested loops.
• Space Complexity: O(amount), due to the dp array. This space can't be optimized further since we need to store the number of combinations for each amount from 0 to amount.