Problem

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.

OR

Count Number of ways of representing n cents using quarters, dimes, nickels and pennies (infinite supply)

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3

1
2

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

Solution

The problem deals with non-canonical systems, and as it has infinite supply of coins, its like unbounded Knapsack. For canonical systems, greedy works.

Method 1 - Recursion

Intuition

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.

Approach

  1. 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).
  2. The recursion tree avoids duplicates by only considering coins at or after the current index.

Example & Image

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.

Complexity

  • ⏰ 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).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
	int change(int amount, vector<int>& coins) {
		return dfs(amount, coins, 0);
	}
private:
	int dfs(int amount, vector<int>& coins, int idx) {
		if (amount < 0) return 0;
		if (amount == 0) return 1;
		if (idx == coins.size()) return 0;
		int count = dfs(amount, coins, idx + 1);
		count += dfs(amount - coins[idx], coins, idx);
		return count;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

type Solution struct{}
func change(amount int, coins []int) int {
	var dfs func(int, int) int
	dfs = func(a, idx int) int {
		if a < 0 { return 0 }
		if a == 0 { return 1 }
		if idx == len(coins) { return 0 }
		count := dfs(a, idx+1)
		count += dfs(a-coins[idx], idx)
		return count
	}
	return dfs(amount, 0)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	public int change(int amount, int[] coins) {
		return dfs(amount, coins, 0);
	}
	private int dfs(int amount, int[] coins, int idx) {
		if (amount < 0) return 0;
		if (amount == 0) return 1;
		if (idx == coins.length) return 0;
		int count = dfs(amount, coins, idx + 1);
		count += dfs(amount - coins[idx], coins, idx);
		return count;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	fun change(amount: Int, coins: IntArray): Int {
		fun dfs(a: Int, idx: Int): Int {
			if (a < 0) return 0
			if (a == 0) return 1
			if (idx == coins.size) return 0
			var count = dfs(a, idx + 1)
			count += dfs(a - coins[idx], idx)
			return count
		}
		return dfs(amount, 0)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
	def change(self, amount: int, coins: list[int]) -> int:
		def dfs(a: int, idx: int) -> int:
			if a < 0:
				return 0
			if a == 0:
				return 1
			if idx == len(coins):
				return 0
			count = dfs(a, idx + 1)
			count += dfs(a - coins[idx], idx)
			return count
		return dfs(amount, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
	pub fn change(amount: i32, coins: Vec<i32>) -> i32 {
		fn dfs(a: i32, idx: usize, coins: &Vec<i32>) -> i32 {
			if a < 0 { return 0; }
			if a == 0 { return 1; }
			if idx == coins.len() { return 0; }
			let mut count = dfs(a, idx + 1, coins);
			count += dfs(a - coins[idx], idx, coins);
			count
		}
		dfs(amount, 0, &coins)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	change(amount: number, coins: number[]): number {
		function dfs(a: number, idx: number): number {
			if (a < 0) return 0;
			if (a === 0) return 1;
			if (idx === coins.length) return 0;
			let count = dfs(a, idx + 1);
			count += dfs(a - coins[idx], idx);
			return count;
		}
		return dfs(amount, 0);
	}
}

Method 2 - DP Solution Top Down With Memo

Intuition

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.

Approach

  1. Create a DP table dp[idx][amount] to store the number of ways to make up amount using coins from index idx onwards.
  2. Use recursion similar to Method 1, but check and store results in the DP table to avoid recomputation.
  3. For each call:
    • If amount < 0, return 0 (invalid).
    • If amount == 0, return 1 (valid combination).
    • If result is already computed, return it.
    • Otherwise, compute by skipping or using the current coin, and store the result.

Complexity

  • ⏰ Time complexity: O(n * amount) — There are n coin indices and amount possible values, and each state is computed only once.
  • 🧺 Space complexity: O(n * amount) — The DP table stores results for each combination of coin index and amount.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
	int change(int amount, vector<int>& coins) {
		int n = coins.size();
		vector<vector<int>> dp(n, vector<int>(amount + 1, -1));
		return dfs(amount, coins, 0, dp);
	}
private:
	int dfs(int amount, vector<int>& coins, int idx, vector<vector<int>>& dp) {
		if (amount < 0) return 0;
		if (amount == 0) return 1;
		if (idx == coins.size()) return 0;
		if (dp[idx][amount] != -1) return dp[idx][amount];
		int count = dfs(amount, coins, idx + 1, dp);
		count += dfs(amount - coins[idx], coins, idx, dp);
		dp[idx][amount] = count;
		return count;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

type Solution struct{}
func change(amount int, coins []int) int {
	n := len(coins)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, amount+1)
		for j := range dp[i] {
			dp[i][j] = -1
		}
	}
	var dfs func(int, int) int
	dfs = func(a, idx int) int {
		if a < 0 { return 0 }
		if a == 0 { return 1 }
		if idx == n { return 0 }
		if dp[idx][a] != -1 { return dp[idx][a] }
		count := dfs(a, idx+1)
		count += dfs(a-coins[idx], idx)
		dp[idx][a] = count
		return count
	}
	return dfs(amount, 0)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
	public int change(int amount, int[] coins) {
		int n = coins.length;
		int[][] dp = new int[n][amount + 1];
		for (int i = 0; i < n; i++) Arrays.fill(dp[i], -1);
		return dfs(amount, coins, 0, dp);
	}
	private int dfs(int amount, int[] coins, int idx, int[][] dp) {
		if (amount < 0) return 0;
		if (amount == 0) return 1;
		if (idx == coins.length) return 0;
		if (dp[idx][amount] != -1) return dp[idx][amount];
		int count = dfs(amount, coins, idx + 1, dp);
		count += dfs(amount - coins[idx], coins, idx, dp);
		dp[idx][amount] = count;
		return count;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
	fun change(amount: Int, coins: IntArray): Int {
		val n = coins.size
		val dp = Array(n) { IntArray(amount + 1) { -1 } }
		fun dfs(a: Int, idx: Int): Int {
			if (a < 0) return 0
			if (a == 0) return 1
			if (idx == n) return 0
			if (dp[idx][a] != -1) return dp[idx][a]
			var count = dfs(a, idx + 1)
			count += dfs(a - coins[idx], idx)
			dp[idx][a] = count
			return count
		}
		return dfs(amount, 0)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
	def change(self, amount: int, coins: list[int]) -> int:
		n = len(coins)
		dp = [[-1 for _ in range(amount + 1)] for _ in range(n)]
		def dfs(a: int, idx: int) -> int:
			if a < 0:
				return 0
			if a == 0:
				return 1
			if idx == n:
				return 0
			if dp[idx][a] != -1:
				return dp[idx][a]
			count = dfs(a, idx + 1)
			count += dfs(a - coins[idx], idx)
			dp[idx][a] = count
			return count
		return dfs(amount, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
	pub fn change(amount: i32, coins: Vec<i32>) -> i32 {
		let n = coins.len();
		let mut dp = vec![vec![-1; (amount + 1) as usize]; n];
		fn dfs(a: i32, idx: usize, coins: &Vec<i32>, dp: &mut Vec<Vec<i32>>) -> i32 {
			if a < 0 { return 0; }
			if a == 0 { return 1; }
			if idx == coins.len() { return 0; }
			if dp[idx][a as usize] != -1 { return dp[idx][a as usize]; }
			let mut count = dfs(a, idx + 1, coins, dp);
			count += dfs(a - coins[idx], idx, coins, dp);
			dp[idx][a as usize] = count;
			count
		}
		dfs(amount, 0, &coins, &mut dp)
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
	change(amount: number, coins: number[]): number {
		const n = coins.length;
		const dp: number[][] = Array.from({length: n}, () => Array(amount + 1).fill(-1));
		function dfs(a: number, idx: number): number {
			if (a < 0) return 0;
			if (a === 0) return 1;
			if (idx === n) return 0;
			if (dp[idx][a] !== -1) return dp[idx][a];
			let count = dfs(a, idx + 1);
			count += dfs(a - coins[idx], idx);
			dp[idx][a] = count;
			return count;
		}
		return dfs(amount, 0);
	}
}

Method 3 - Bottom up DP

Intuition

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.

Approach

  1. Create a DP table dp[i][j] where i is the number of coins considered and j is the current amount.
  2. Initialize dp[i][0] = 1 for all i (one way to make amount 0: use no coins).
  3. For each coin and each amount:
    • Set dp[i][j] = dp[i-1][j] (skip current coin).
    • If j >= coins[i-1], add dp[i][j - coins[i-1]] (use current coin).
  4. The answer is dp[n][amount].

Complexity

  • ⏰ Time complexity: O(n * amount) — We fill a table of size n * amount, where n is the number of coins.
  • 🧺 Space complexity: O(n * amount) — The DP table stores results for each coin and amount combination.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
	int change(int amount, vector<int>& coins) {
		int n = coins.size();
		vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
		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
15
16
17
18

type Solution struct{}
func change(amount int, coins []int) int {
	n := len(coins)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, amount+1)
		dp[i][0] = 1
	}
	for i := 1; i <= n; i++ {
		for 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

class Solution {
	public int change(int amount, int[] coins) {
		int n = coins.length;
		int[][] dp = new int[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

class Solution {
	fun change(amount: Int, coins: IntArray): Int {
		val n = coins.size
		val dp = Array(n + 1) { IntArray(amount + 1) }
		for (i in 0..n) dp[i][0] = 1
		for (i in 1..n) {
			for (j in 1..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

class Solution:
	def change(self, amount: int, coins: list[int]) -> int:
		n = len(coins)
		dp = [[0 for _ in range(amount + 1)] for _ in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for 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 {
	pub fn change(amount: i32, coins: Vec<i32>) -> i32 {
		let n = coins.len();
		let mut dp = vec![vec![0; (amount + 1) as usize]; n + 1];
		for i in 0..=n { dp[i][0] = 1; }
		for i in 1..=n {
			for j in 1..=(amount as usize) {
				dp[i][j] = dp[i-1][j];
				if j as i32 >= coins[i-1] {
					dp[i][j] += dp[i][j - coins[i-1] as usize];
				}
			}
		}
		dp[n][amount as usize]
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
	change(amount: number, coins: number[]): number {
		const n = coins.length;
		const dp: number[][] = Array.from({length: n + 1}, () => Array(amount + 1).fill(0));
		for (let i = 0; i <= n; i++) dp[i][0] = 1;
		for (let i = 1; i <= n; i++) {
			for (let 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];
	}
}

Method 4 - Bottom Up DP - Optimized Space

Intuition

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.

Approach

  1. Initialize a 1D DP array dp of size amount + 1 with dp[0] = 1 (one way to make amount 0).
  2. For each coin, iterate through all amounts from the coin value up to amount:
    • For each j, add dp[j - coin] to dp[j].
  3. After processing all coins, dp[amount] contains the answer.

Complexity

  • ⏰ Time complexity: O(n * amount) — We process each coin for every amount.
  • 🧺 Space complexity: O(amount) — Only a single array of size amount + 1 is used.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
	int change(int amount, vector<int>& coins) {
		vector<int> dp(amount + 1, 0);
		dp[0] = 1;
		for (int coin : coins) {
			for (int j = coin; j <= amount; ++j) {
				dp[j] += dp[j - coin];
			}
		}
		return dp[amount];
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

type Solution struct{}
func change(amount int, coins []int) int {
	dp := make([]int, amount+1)
	dp[0] = 1
	for _, coin := range coins {
		for j := coin; j <= amount; j++ {
			dp[j] += dp[j-coin]
		}
	}
	return dp[amount]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
	public int change(int amount, int[] coins) {
		int[] dp = new int[amount + 1];
		dp[0] = 1;
		for (int coin : coins) {
			for (int j = coin; j <= amount; j++) {
				dp[j] += dp[j - coin];
			}
		}
		return dp[amount];
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
	fun change(amount: Int, coins: IntArray): Int {
		val dp = IntArray(amount + 1)
		dp[0] = 1
		for (coin in coins) {
			for (j in coin..amount) {
				dp[j] += dp[j - coin]
			}
		}
		return dp[amount]
	}
}
1
2
3
4
5
6
7
8

class Solution:
	def change(self, amount: int, coins: list[int]) -> int:
		dp = [0] * (amount + 1)
		dp[0] = 1
		for coin in coins:
			for j in range(coin, amount + 1):
				dp[j] += dp[j - coin]
		return dp[amount]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
	pub fn change(amount: i32, coins: Vec<i32>) -> i32 {
		let mut dp = vec![0; (amount + 1) as usize];
		dp[0] = 1;
		for &coin in &coins {
			for j in coin..=amount {
				dp[j as usize] += dp[(j - coin) as usize];
			}
		}
		dp[amount as usize]
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
	change(amount: number, coins: number[]): number {
		const dp: number[] = Array(amount + 1).fill(0);
		dp[0] = 1;
		for (const coin of coins) {
			for (let j = coin; j <= amount; j++) {
				dp[j] += dp[j - coin];
			}
		}
		return dp[amount];
	}
}