Skip to content
AI360Xpert
Back to 2-D Dynamic Programming
Medium

Coin Change II

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

Input:amount = 5, coins = [1,2,5]
Output:4
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
Input:amount = 3, coins = [2]
Output:0
The amount of 3 cannot be made up just with coins of 2.
Input:amount = 10, coins = [10]
Output:1
10=10

Constraints

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • All the values of coins are unique.
  • 0 <= amount <= 5000

Dynamic Programming (1D Array)

Approach

This problem is similar to the Unbounded Knapsack problem. We can use a 1D DP array where `dp[a]` represents the number of ways to make up amount `a`. We initialize `dp[0] = 1` because there is exactly 1 way to make the amount 0 (using no coins). We iterate over each coin. For a specific coin, we update the `dp` array for all amounts from the coin's value up to the target amount. The number of ways to make amount `a` is incremented by the number of ways to make amount `a - coin`.

Complexity Analysis

Time Complexity
O(amount * len(coins))
Space Complexity
O(amount)

Iterating over coins in the outer loop ensures we find combinations rather than permutations (e.g., 1+2 vs 2+1). Time complexity is O(N * M) and space complexity is O(N) where N is the amount and M is the number of coins.

Solution.java
class Solution {    public int change(int amount, int[] coins) {        int[] dp = new int[amount + 1];        dp[0] = 1; // 1 way to make amount 0                // Loop over each coin first (outer loop)        for (int coin : coins) {            // Update ways for all amounts that can include this coin            for (int a = coin; a <= amount; a++) {                dp[a] += dp[a - coin];            }        }                return dp[amount];    }}