Coin Change Permutations

Fastrail08

May 20th, 2025

200

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 3.50 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
//QUESTION - https://www.youtube.com/watch?v=yc0LunmJA1A&list=PL-Jc9J83PIiG8fE6rj9F5a6uyQ5WPdqKy&index=14 (COIN CHANGE PERMUTATIONS)
//To memoise the code, figure out the param that is changing at every state and can be used to UNIQUELY identify all the states, so that the answer could be stored against it.
// Here amount is the param that can be memoised, as it can UNIQUELY identify all the states.
//How many ways to pay up given amount, when you currently have x amount.
// Recursive code + memo
int getAllCoinChangePerm(int level, int &amount, vector<int> &coins, string currPerm, vector<int> &memo){
if(level > amount){
return 0;
}
if(level == amount){
// You can't print if you memoise the code, because printing happens at base case, and memoised code avoid going to base case each time, if you have answer already
// cout << currPerm << '\n';
return 1;
}
if(memo[level] != 0){
return memo[level];
}
// level = amount made
//options = try each currency to form all the possible permutations to reach amount
int totalWays = 0;
for(int i = 0; i < coins.size(); i++){
totalWays += getAllCoinChangePerm(level + coins[i], amount, coins, currPerm + to_string(coins[i]), memo);
}
return memo[level] = totalWays;
}
int getAllCoinChangePermDP(int &amount, vector<int> &coins){
// Storage & Meaning - dp[i] = how many ways to pay 'amount' if you already have dp[i] amount
vector<int> dp(amount + 1, 0);
//Direction - figure out where the smallest problem lie(base case in recursion), initialise it, & build up to larger problems
//smallest problem = dp[amount] = 1, you have 1 way to pay amount, if you are already dp[amount], pay nothing so 1 way
dp[amount] = 1;
//Travel & Solve - Travel towards to larger problem, build answer for larger problems, by analysing the recursion tree, by checking what calls are made on the way up (smaller problem -> larger problems)
//NOTE-IMPORTANT
//IN recursion we went down from larger problems to smaller problems, just see the tree, and figure out what's the relationship between the parent and child states in TERMS OF MEMOISED PARAMS. Exactly those calls will be made in dp array.
//For Eg - nth fib calls to 2 children states (n - 1) and (n - 2) while going down the recursive tree
//DP solves on the way up on recursion tree, you will have answers to all the smaller problems. Now you just need to figure out what smaller problems to call to get the values for the current state and that would exactly be the calls in recursion tree (parent -> child in recursion, child-> parent in DP)
// In DP, the answer for nth fib will be a call to (n - 1) & (n - 2)
//Alternatively you could also think as..
//dp[n] will be responsible for BUILDING the answer for dp[n + 1] & dp[n + 2] (IMPLEMENT THIS)
for(int i = amount - 1; i >= 0; i--){
for(int j = 0; j < coins.size(); j++){
if(i + coins[j] <= amount){
dp[i] += dp[i + coins[j]];
}
}
}
return dp[0];
}
int main() {
// your code goes here
int n, amt;
cin >> n;
vector<int> coins(n);
for(int i = 0; i < n; i++){
cin >> coins[i];
}
cin >> amt;
vector<int> memo(amt + 1, 0);
cout << getAllCoinChangePerm(0, amt, coins, "", memo) << '\n';
cout << getAllCoinChangePermDP(amt, coins) << '\n';
}

Add Comment

Please, Sign In to add comment