The problem deals with non-canonical systems, and as it has infinite supply of coins, its like unbounded Knapsack. For canonical systems, greedy works.
This problem is similar to the unbounded knapsack, where you can use each coin as many times as needed. To avoid counting duplicate combinations (e.g., [1,2,2] and [2,1,2]), we always move forward in the coin list, ensuring each combination is unique regardless of order.
Use recursion to explore all possible ways to make up the amount:
At each step, you can either skip the current coin and move to the next, or use the current coin and stay at the same index (since coins can be reused).
If the amount becomes negative, return 0 (invalid path).
If the amount becomes zero, return 1 (valid combination found).
The recursion tree avoids duplicates by only considering coins at or after the current index.
When we choose a coin i (e.g., [1,2,5]), we choose 1, then we can choose 2, etc. If we choose 2, we should not go back to 1 in the same path, as it may cause duplicates.
See the tree below:
---
title: amount = 5, coins = [1,2,5]
---
graph TD;
A(0) ---|1| B(1)
A ---|2| C(2)
A ---|5| D(5)
B --- E(2) --- F(2)
C --- H(1) --- I(2)
So, [1,2,2] and [2, 1, 2] are the same solution. To avoid such duplicates, we use the index to move forward and only take coins at or after the current index for each solution.
⏰ Time complexity:O(2^n * amount) — In the worst case, each coin can be either included or excluded at each step, leading to exponential combinations. The recursion explores all possible subsets and amounts.
🧺 Space complexity:O(amount) — The maximum depth of the recursion stack is up to the amount (if we keep subtracting the smallest coin).
We use memoization to avoid redundant calculations in the recursion tree. By storing results for each state (idx, amount), we ensure that each subproblem is solved only once, making the solution efficient for larger inputs.
This method uses dynamic programming to build up the solution iteratively. We fill a DP table where each entry dp[i][j] represents the number of ways to make up amount j using the first i coins. By considering both skipping and using each coin, we ensure all combinations are counted without duplicates.
classSolution {
publicintchange(int amount, int[] coins) {
int n = coins.length;
int[][] dp =newint[n + 1][amount + 1];
for (int i = 0; i <= n; i++) dp[i][0]= 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= amount; j++) {
dp[i][j]= dp[i - 1][j];
if (j >= coins[i - 1]) dp[i][j]+= dp[i][j - coins[i - 1]];
}
}
return dp[n][amount];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution {
funchange(amount: Int, coins: IntArray): Int {
val n = coins.size
val dp = Array(n + 1) { IntArray(amount + 1) }
for (i in0..n) dp[i][0] = 1for (i in1..n) {
for (j in1..amount) {
dp[i][j] = dp[i-1][j]
if (j >= coins[i-1]) dp[i][j] += dp[i][j - coins[i-1]]
}
}
return dp[n][amount]
}
}
1
2
3
4
5
6
7
8
9
10
11
12
classSolution:
defchange(self, amount: int, coins: list[int]) -> int:
n = len(coins)
dp = [[0for _ in range(amount +1)] for _ in range(n +1)]
for i in range(n +1):
dp[i][0] =1for i in range(1, n +1):
for j in range(1, amount +1):
dp[i][j] = dp[i-1][j]
if j >= coins[i-1]:
dp[i][j] += dp[i][j - coins[i-1]]
return dp[n][amount]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Solution {
pubfnchange(amount: i32, coins: Vec<i32>) -> i32 {
let n = coins.len();
letmut dp =vec![vec![0; (amount +1) asusize]; n +1];
for i in0..=n { dp[i][0] =1; }
for i in1..=n {
for j in1..=(amount asusize) {
dp[i][j] = dp[i-1][j];
if j asi32>= coins[i-1] {
dp[i][j] += dp[i][j - coins[i-1] asusize];
}
}
}
dp[n][amount asusize]
}
}
We can optimize the space used in the bottom-up DP approach by realizing that we only need the previous row and the current row at any time. By reusing a 1D array and updating it in place for each coin, we reduce the space complexity from O(n * amount) to O(amount). This works because for each coin, the number of ways to make up each amount only depends on the current and previous states.
In a canonical coin system (e.g., US coins [1, 5, 10, 25]) a well‑known property is that the greedy strategy yields an optimal solution for the minimum number of coins variant. If you are interested in that problem, read here: Coin Change with Fewest Number of Coins Given Canonical System and Infinite Supply. However, for the counting variant (this problem) the DP recurrence and implementation are identical for canonical and non‑canonical sets:
We still want the number of unordered combinations (order does not matter).
We still prevent overcounting by iterating coins in an outer loop and amounts ascending in the inner loop (1D) or by indexing forward in recursion.
Canonical structure only impacts the optimality of a greedy algorithm for the min‑coins objective, not the counting objective (there is no greedy shortcut for counting because you must enumerate combinatorial structure implicitly).
Therefore the separate “canonical” counting problem collapses to this generic formulation. The only differences you may sometimes see in legacy write‑ups are:
Hard‑coded denomination sequence (quarters, dimes, nickels, pennies) instead of a parameterized coins array.
A recursive function that switches on the current denomination to pick the next smaller one. This is just a specialized way to iterate the sorted list; its complexity and recurrence are the same.
For example, number of ways to make 100 cents with US coins can be computed with the same 1D DP:
dp[0] = 1; for coin in [1,5,10,25]: for amount from coin..100: dp[amount] += dp[amount-coin]. Final answer dp[100] = 242.