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.
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 just with coins of 2.
Example 3:
Input: amount = 10, coins = [10]
Output: 1
Constraints
1 <= coins.length <= 3001 <= coins[i] <= 5000- All the values of coins are unique.
0 <= amount <= 5000
Approach:
- Recursion with Memoization
- Define a function
fn(remS, start)→ number of ways to makeremSusing coins from indexstartonward. - Use
dp[remS][start]to cache results and avoid recomputation.
- Define a function
- Base cases are:
- If
remS == 0→ found 1 valid combination → return1. - If
remS < 0→ no valid way → return0.
- If
- From index
startto end, try picking each coin:combinations += fn(remS - coins[i], i) // i instead of i+1 because coins[i] can be reused - At last, Call
fn(amount, 0)→ total number of unique combinations to makeamount.
Time & Space Complexity:
Time Complexity: O(amount * n)
Space Complexity: O(amount * n)
Dry Run
Input: amount = 5, coins = [1, 2, 5]
Initial:
n = 3
dp rows 0..5 × cols 0..2 initialized to -1
Call fn(remS = 5, start = 0)
fn(5,0):
combinations = 0
i = 0 → call fn(4,0)
i = 1 → call fn(3,1)
i = 2 → call fn(0,2)
fn(4,0):
combinations = 0
i = 0 → fn(3,0)
i = 1 → fn(2,1)
i = 2 → fn(-1,2) = 0
fn(3,0):
combinations = 0
i = 0 → fn(2,0)
i = 1 → fn(1,1)
i = 2 → fn(-2,2) = 0
fn(2,0):
combinations = 0
i = 0 → fn(1,0)
i = 1 → fn(0,1) = 1
i = 2 → fn(-3,2) = 0
fn(1,0):
combinations = 0
i = 0 → fn(0,0) = 1
i = 1 → fn(-1,1) = 0
i = 2 → fn(-4,2) = 0
→ combinations = 1
dp[1][0] = 1
return 1
Back in fn(2,0):
- from i=0 got 1 (fn(1,0))
- from i=1 got 1 (fn(0,1))
→ combinations = 1 + 1 = 2
dp[2][0] = 2
return 2
Back in fn(3,0):
- from i=0 got 2 (fn(2,0))
- fn(1,1) next:
fn(1,1):
i = 1 → fn(-1,1) = 0
i = 2 → fn(-4,2) = 0
→ combinations = 0
dp[1][1] = 0
return 0
→ fn(3,0) combinations = 2 + 0 + 0 = 2
dp[3][0] = 2
return 2
fn(2,1):
i = 1 → fn(0,1) = 1
i = 2 → fn(-3,2) = 0
→ combinations = 1
dp[2][1] = 1
return 1
Back in fn(4,0):
- from i=0 → fn(3,0) = 2
- from i=1 → fn(2,1) = 1
- i=2 → 0
→ combinations = 2 + 1 = 3
dp[4][0] = 3
return 3
fn(3,1) (from fn(5,0) i=1):
check dp[3][1] — not set
i=1 → fn(1,1) = 0 (from earlier)
i=2 → fn(-2,2) = 0
→ combinations = 0
dp[3][1] = 0
return 0
fn(0,2) (from fn(5,0) i=2):
remS === 0 → return 1
Back in fn(5,0):
- from i=0 → fn(4,0) = 3
- from i=1 → fn(3,1) = 0
- from i=2 → fn(0,2) = 1
→ combinations = 3 + 0 + 1 = 4
dp[5][0] = 4
return 4
Some dp entries filled:
dp[1][0] = 1
dp[2][0] = 2
dp[3][0] = 2
dp[1][1] = 0
dp[2][1] = 1
dp[3][1] = 0
dp[4][0] = 3
dp[5][0] = 4
Final:
fn(5,0) = 4
(combinations: [1+1+1+1+1], [1+1+1+2], [1+2+2], [5])
Output: 4
var change = function(amount, coins) {
let n = coins.length;
let dp = Array.from({length: amount + 1}, () => Array(n).fill(-1));
let fn = (remS, start) => {
if(remS === 0) return 1;
if(remS < 0) return 0;
if(dp[remS][start] != -1) return dp[remS][start];
let combinations = 0;
for(let i=start; i < n; i++){
combinations += fn(remS - coins[i], i);
}
return dp[remS][start] = combinations;
}
return fn(amount, 0);
};
def change(amount, coins):
n = len(coins)
if n == 0:
return 1 if amount == 0 else 0
dp = [[-1] * n for _ in range(amount + 1)]
def fn(rem, start):
if rem == 0:
return 1
if rem < 0:
return 0
if dp[rem][start] != -1:
return dp[rem][start]
combinations = 0
for i in range(start, n):
combinations += fn(rem - coins[i], i)
dp[rem][start] = combinations
return combinations
return fn(amount, 0)
public class Solution {
public long change(int amount, int[] coins) {
int n = coins.length;
if (n == 0) return amount == 0 ? 1L : 0L;
long[][] dp = new long[amount + 1][n];
for (int i = 0; i <= amount; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = -1;
}
}
return fn(amount, 0, coins, dp);
}
private long fn(int rem, int start, int[] coins, long[][] dp) {
if (rem == 0) return 1;
if (rem < 0) return 0;
if (dp[rem][start] != -1) return dp[rem][start];
long combinations = 0;
for (int i = start; i < coins.length; i++) {
combinations += fn(rem - coins[i], i, coins, dp);
}
dp[rem][start] = combinations;
return combinations;
}
}
#include <bits/stdc++.h>
using namespace std;
long long change_helper(int rem, int start, const vector& coins, vector>& dp) {
if (rem == 0) return 1;
if (rem < 0) return 0;
if (dp[rem][start] != -1) return dp[rem][start];
long long combinations = 0;
int n = coins.size();
for (int i = start; i < n; ++i) {
combinations += change_helper(rem - coins[i], i, coins, dp);
}
dp[rem][start] = combinations;
return combinations;
}
long long change(int amount, vector& coins) {
int n = coins.size();
if (n == 0) return (amount == 0) ? 1 : 0;
vector> dp(amount + 1, vector(n, -1));
return change_helper(amount, 0, coins, dp);
}
#include <stdio.h>
#include <stdlib.h>
long long fn_helper(int rem, int start, int *coins, int n, long long *dp) {
if (rem == 0) return 1;
if (rem < 0) return 0;
long long idx = (long long)rem * n + start;
if (dp[idx] != -1) return dp[idx];
long long combinations = 0;
for (int i = start; i < n; ++i) {
combinations += fn_helper(rem - coins[i], i, coins, n, dp);
}
dp[idx] = combinations;
return combinations;
}
long long change(int amount, int *coins, int n) {
if (n == 0) return amount == 0 ? 1LL : 0LL;
long long total = (long long)(amount + 1) * n;
long long *dp = (long long*)malloc(sizeof(long long) * total);
if (!dp) return 0; // out of memory, simple handling
for (long long i = 0; i < total; ++i) dp[i] = -1;
long long res = fn_helper(amount, 0, coins, n, dp);
free(dp);
return res;
}
using System;
public class Solution {
public long Change(int amount, int[] coins) {
int n = coins.Length;
if (n == 0) return amount == 0 ? 1L : 0L;
long[,] dp = new long[amount + 1, n];
for (int i = 0; i <= amount; i++)
for (int j = 0; j < n; j++)
dp[i, j] = -1;
long Fn(int rem, int start) {
if (rem == 0) return 1;
if (rem < 0) return 0;
if (dp[rem, start] != -1) return dp[rem, start];
long combinations = 0;
for (int i = start; i < n; i++) {
combinations += Fn(rem - coins[i], i);
}
dp[rem, start] = combinations;
return combinations;
}
return Fn(amount, 0);
}
}
