Problem Overview

You are given an integer amount representing a total sum of money and an integer array coins representing the denominations of available coins.
Your task is to find the number of combinations that make up the given amount using any number of coins.
Each coin can be used unlimited times, but the order of coins doesn’t matter (i.e., {1,2} and {2,1} are the same combination).

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: There are four combinations:
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: No combination can make up 3 using only coin 2.

Example 3:

Input: amount = 10, coins = [10]
Output: 1
Explanation: Only one combination (10 = 10).

Constraints:

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• 0 <= amount <= 5000

---

Intuition / Approach

This is a Dynamic Programming (DP) problem — it’s similar to the classic unbounded knapsack problem.

The key idea is:

• For each coin, determine how many ways you can form every amount from 0 to amount.
• If you can use the same coin multiple times, then the subproblem relation builds upon itself using previous states.

We define dp[i] as the number of combinations to make up amount i.

Thought Process:

1. Start with dp[0] = 1, because there’s exactly one way to make amount 0 — by choosing no coins.
2. For each coin, iterate through all possible amounts from that coin’s value up to the target amount.
3. For each amount i, add the number of combinations that make up i - coin to dp[i].
   This means you’re including one more coin of that type to extend the existing combinations.

---

Algorithm Steps

1. Initialize a dp array of size amount + 1 with all elements 0.
2. Set dp[0] = 1.
3. Loop over each coin in coins:
   • For each value from coin to amount:
     • Update dp[i] += dp[i - coin].
4. After processing all coins, dp[amount] will contain the number of combinations.

---

Java Code Implementation

public class CoinChangeII {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1; // One way to make amount 0 — no coins

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

        return dp[amount];
    }

    public static void main(String[] args) {
        CoinChangeII solution = new CoinChangeII();
        System.out.println(solution.change(5, new int[]{1, 2, 5})); // Output: 4
        System.out.println(solution.change(3, new int[]{2}));       // Output: 0
        System.out.println(solution.change(10, new int[]{10}));     // Output: 1
    }
}

---

Step-by-Step Example

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

Initially:

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

After using coin = 1:

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

After using coin = 2:

dp = [1, 1, 2, 2, 3, 3]

After using coin = 5:

dp = [1, 1, 2, 2, 3, 4]

So, there are 4 combinations to make 5.

---

Complexity Analysis

Time Complexity: O(amount * number_of_coins)

• For each coin, we iterate through all amounts up to amount.

Space Complexity: O(amount)

• We maintain a one-dimensional DP array of size amount + 1.

---

Alternative Approach: 2D DP Table (for clarity)

We can also use a 2D DP table dp[i][j], where i is the number of coins considered and j is the target amount.

Formula:

dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]

• dp[i - 1][j]: excluding current coin.
• dp[i][j - coins[i - 1]]: including current coin.

Though conceptually easier, this takes O(n * amount) space, so the 1D version is preferred.