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'll create a DP table (array) dp of size amount + 1. dp[i] will store the number of combinations to make up the amount i.

2. Initialization: Initialize dp[0] to 1 (there's one way to make up amount 0: using no coins). The rest of the dp array is initialized to 0.

3. Iteration: Iterate through each coin in coins. For each coin c, iterate through the dp array from c to amount. For each index i, dp[i] will be updated by adding dp[i - c]. This is because if we can make up the amount i - c, we can also make up the amount i by adding coin c.

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

Explanation:

The dynamic programming approach cleverly avoids redundant calculations. It builds up the solution iteratively. For each coin, it considers all possible ways to include that coin in forming the target amount. The addition dp[i] += dp[i - c] ensures we are counting all combinations, not just permutations.

Code (Typescript):

function change(amount: number, coins: number[]): number {
    const dp: number[] = new Array(amount + 1).fill(0);
    dp[0] = 1; // Base case: one way to make amount 0

    for (const coin of coins) {
        for (let 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 uses space proportional to the amount.