This problem is similar to the unbounded knapsack where we have the choice to pick item any number of time
1: Here we can start pick a coin either from starting index or from last
2: For every coin we have two choices either to include it or exclude it depending upon the amount needed
3: if (coin[i] > amount) then shift to next index.
or if (amount >= coin[i]) we have the choice the include it or exclude it.
- if we include it , we again have the choice the include it any number of time => we will not move to the next index
Brute Force (Recurrsive Approach) => TLE
class Solution {
public:
int combinations(int amount , vector <int> &coins , int i){
if(i == 0){
return 0;
}
if(amount == 0){
return 1;
}
if(coins[i-1] <= amount){
return combinations(amount- coins[i-1] , coins, i) + combinations(amount, coins, i-1);
}else{
return combinations(amount , coins, i-1);
}
}
int change(int amount, vector<int>& coins) {
int n = coins.size();
return combinations(amount, coins, n);
}
};Memoize the solution to avoid repitive recursive calls
Store already computed recursive calls and use it if called again thus time complexity gets reduced
Time Complexity- O(amount*n)
Space Complexity - O(amount*n)
class Solution {
public:
int combinations(int amount , vector <int> &coins , int i , vector <vector <int>> &dp){
if(i == 0){
return 0;
}
if(amount == 0){
return 1;
}
if(dp[i][amount] != -1){
return dp[i][amount];
}
if(coins[i-1] <= amount){
return dp[i][amount] = combinations(amount- coins[i-1] , coins, i, dp) + combinations(amount, coins, i-1 ,dp);
}else{
return dp[i][amount] = combinations(amount , coins, i-1, dp);
}
}
int change(int amount, vector<int>& coins) {
int n = coins.size();
vector <vector <int>> dp(n+1, vector <int> (amount+1, -1));
return combinations(amount, coins, n, dp);
}
};Tabulations Method Bottom Up Approach
Time Complexity- O(amount*n)
Space Complexity - O(amount*n)
class Solution {
public:
int change(int amount, vector<int>& coins) {
int n = coins.size();
if(n == 0){
return 0;
}
if(amount == 0){
return 1;
}
vector <vector <int>> dp(n+1, vector <int> (amount+1, 0));
// When amount is zero
for(int i = 0; i < n+1; i++){
dp[i][0] = 1;
}
//When amount and coins are both zero
dp[0][0] = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <=amount; j++){
if(coins[i-1] > j){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j];
}
}
}
return dp[n][amount];
}
};