Problem
Given an integer array coins representing different coin denominations and an integer amount, return the number of combinations that make up the given amount.You may use each coin an unlimited number of times. The order of coins does not matter, so
[1,2] and [2,1] represent the same combination.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
amount = 5
coins = [1,2,5]Output
4Example 2
Input
amount = 3
coins = [2]Output
0Solution
This solution uses the Dynamic Programming pattern with Top-Down Memoization. We usememo[amount][i] to store the number of combinations possible for the remaining amount using coins starting from index i.
At each step, we have two choices. We can use the current coin, in which case we keep the same index because the coin can be used unlimited times. Or we can skip the current coin and move to the next coin.
When
amount == 0, we have formed a valid combination, so we return 1. If we run out of coins or the amount becomes negative, there is no valid combination, so we return 0.
class Solution {
public int change(int amount, int[] coins) {
Integer[][] memo = new Integer[amount + 1][coins.length];
return coinChange(coins, amount, 0, memo);
}
private int coinChange(int[] coins, int amount, int i, Integer[][] memo) {
// Exact amount formed.
if (amount == 0) {
return 1;
}
// No coins left or amount exceeded.
if (i >= coins.length || amount < 0) {
return 0;
}
// Return the already calculated result.
if (memo[amount][i] != null) {
return memo[amount][i];
}
// Use the current coin or skip it.
return memo[amount][i] =
coinChange(coins, amount - coins[i], i, memo)
+ coinChange(coins, amount, i + 1, memo);
}
}Complexity
There are(amount + 1) × n possible states, where n is the number of coins. Each state is calculated once, so the time complexity is O(amount × n).
The memoization table stores
O(amount × n) states, and the recursion stack can use up to O(amount + n) space. Therefore, the overall space complexity is O(amount × n).