📌 1. Question Analysis

🔍 Problem

Given:

• coins[] — denominations
• amount

Return: 👉 number of combinations that make up the amount
👉 Unlimited coins of each type

💡 Key Observations

• This is NOT asking for minimum → it’s asking for count
• Order does NOT matter:
  • [1,2] and [2,1] are the same combination

🧠 DP Decision

Define: dp[i] = number of ways to make amount i

Base case:: dp[0] = 1

👉 One way to make 0: choose nothing

🔁 Transition

dp[i] += dp[i - coin]

Meaning:

• ways to make i
• += ways to make i - coin then add this coin

⚠️ Loop Order (VERY IMPORTANT)

for coin in coins:
for i from coin → amount:

👉 Ensures combinations (not permutations)

🚀 2. Solution

💻 Code (TypeScript)

function change(amount: number, coins: number[]): number {
    const dp = new Array(amount + 1).fill(0);

    dp[0] = 1;

    for (const coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }

    return dp[amount];
}

⏱ Complexity

• Time: O(amount × number of coins)
• Space: O(amount)

🔍 3. Walkthrough

Example:

amount = 5
coins = [1,2,5]

Step 1: Initialize

dp = [1, 0, 0, 0, 0, 0]

Step 2: Use coin = 1

dp = [1, 1, 1, 1, 1, 1]

Step 3: Use coin = 2

dp[2] += dp[0] → 2
dp[3] += dp[1] → 2
dp[4] += dp[2] → 3
dp[5] += dp[3] → 3
dp = [1, 1, 2, 2, 3, 3]

Step 4: Use coin = 5

dp[5] += dp[0] → 4
dp = [1, 1, 2, 2, 3, 4]

✅ Final Answer

4

🧠 Key Takeaways

• Counting problem → use +=
• dp[0] = 1 is critical
• Coin-first loop avoids duplicate permutations