Coin Change II

MediumDynamic ProgrammingArray
Category: 2-D Dynamic Programming
Companies that ask this question:
AmazonGoogleFacebook

Approach

Coin Change II

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 answer is guaranteed to fit into a signed 32-bit integer.

Examples

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 with just coins of 2.

Example 3:

Input: amount = 10, coins = [10]
Output: 1

Approach: Dynamic Programming

Intuition

This is a classic unbounded knapsack problem where we can use each coin unlimited times. The key insight is that the order of coins doesn't matter (combinations, not permutations).

Key Insight:

  • For each coin, we decide how many times to use it
  • Process coins one at a time to avoid counting duplicate combinations
  • dp[i] = number of ways to make amount i

Algorithm

  1. Create a 1D DP array of size amount + 1:

    • dp[i] = number of combinations to make amount i

  2. Initialize base case:

    • dp[0] = 1 (one way to make 0: use no coins)

  3. For each coin:

    • Update all amounts that can be formed using this coin
    • For each amount i >= coin: 
      dp[i] += dp[i - coin]

  4. Return dp[amount]

Why This Works

  • Processing coins in order prevents counting duplicates
    • Example: [1,2,5] → avoids counting both "1+2" and "2+1"
  • Unbounded knapsack: We can use same coin multiple times
  • dp[i - coin] already includes all ways to use current coin

Complexity Analysis

  • Time Complexity: O(amount × coins.length) - for each coin, update all amounts
  • Space Complexity: O(amount) - 1D DP array
    • 2D version would be O(amount × coins.length)

Common Patterns

This problem demonstrates:

  1. Unbounded Knapsack: Items (coins) can be used unlimited times
  2. Combination Sum: Count combinations, not permutations
  3. 1D DP Optimization: Space-optimized from 2D approach
  4. Coin Change Variant: Related to minimum coin change problem

Related Problems

  • Coin Change (minimum coins)
  • Combination Sum
  • Partition Equal Subset Sum
  • Target Sum

Tips

  1. Order matters: Process coins in order to avoid duplicate combinations
  2. Loop direction: Inner loop goes forward (left to right) for unbounded knapsack
  3. Base case: dp[0] = 1 is crucial
  4. Difference from permutations: If we wanted permutations, we'd loop coins inside amounts

Solution

java
1class Solution {
2    // Solution 1: Dynamic Programming (1D Array)
3    public int change(int amount, int[] coins) {
4        // dp[i] = number of ways to make amount i
5        int[] dp = new int[amount + 1];
6        dp[0] = 1; // One way to make 0: use no coins
7
8        // For each coin
9        for (int coin : coins) {
10            // Update all amounts that can be formed with this coin
11            for (int i = coin; i <= amount; i++) {
12                dp[i] += dp[i - coin];
13            }
14        }
15
16        return dp[amount];
17    }
18
19    // Solution 2: 2D DP (More explicit)
20    public int change2D(int amount, int[] coins) {
21        int n = coins.length;
22        // dp[i][j] = ways to make amount j using first i coins
23        int[][] dp = new int[n + 1][amount + 1];
24
25        // Base case: one way to make amount 0
26        for (int i = 0; i <= n; i++) {
27            dp[i][0] = 1;
28        }
29
30        // Fill the table
31        for (int i = 1; i <= n; i++) {
32            for (int j = 0; j <= amount; j++) {
33                // Don't use current coin
34                dp[i][j] = dp[i - 1][j];
35
36                // Use current coin if possible
37                if (j >= coins[i - 1]) {
38                    dp[i][j] += dp[i][j - coins[i - 1]];
39                }
40            }
41        }
42
43        return dp[n][amount];
44    }
45
46    // Solution 3: Space-Optimized 2D DP
47    public int changeSpaceOptimized(int amount, int[] coins) {
48        int[] prev = new int[amount + 1];
49        int[] curr = new int[amount + 1];
50        prev[0] = 1;
51
52        for (int coin : coins) {
53            curr[0] = 1;
54            for (int j = 1; j <= amount; j++) {
55                curr[j] = prev[j];
56                if (j >= coin) {
57                    curr[j] += curr[j - coin];
58                }
59            }
60            // Swap arrays
61            int[] temp = prev;
62            prev = curr;
63            curr = temp;
64        }
65
66        return prev[amount];
67    }
68}
69
Loading visualizer...