Cacher is the code snippet organizer for pro developers

#include<bits/stdc++.h>
using namespace std;

// #DynamicProgramming #StandardProblem

//==============( TopDown )==============
// https://www.youtube.com/watch?v=k4y5Pr0YVhg
int coinChangeTD(int sum, vector<int> coins, int currInd){
    if(sum==0){
        return 1; // only one way to make change for 0 ( with no coins)
    }
    if(sum<0){
        return 0; // invalid case
    }
    // every stage can be reached from previous stages
    int ways=0;
    // start from currInd to avoid repetetive combinations ex: 211 112
    for(int i=currInd; i<coins.size(); i++){
        ways+=coinChangeTD(sum-coins[i],coins,i);
    }
    return ways;
}
int coinChangeTD(int sum, vector<int> coins){
    return coinChangeTD(sum,coins,0);
}
// Memoization
// https://www.geeksforgeeks.org/coin-change-dp-7/
int coinChange1(int sum, vector<int> coins, int index){
    if(sum==0){
        return 1; // sum=0 can be produced in a single way
    }
    if(index>=coins.size()){
        return 0;
    }
    int with=0;
    if(coins[index] <= sum){ // if we can make change with current coin
        with=coinChange1(sum-coins[index],coins,index);
    }
    int without=coinChange1(sum,coins,index+1);
    return with+without;

}
int coinChange1(int sum, vector<int> coins){
    return coinChange1(sum,coins,0);
}

// https://www.youtube.com/watch?v=sn0DWI-JdNA
int coinChange2(int sum, vector<int> coins, int index){
    if(sum==0){
        return 1;
    }
    if(index>=coins.size()){
        return 0;
    }
    int amountWithCoin=0;
    int ways=0;
    while(amountWithCoin<=sum){
        int remaining=sum-amountWithCoin;
        ways+=coinChange2(remaining,coins,index+1);
        amountWithCoin+=coins[index];
    }
    return ways;
}
int coinChange2(int sum, vector<int> coins){
    return coinChange2(sum,coins,0);
}

//====================( BottomUp )=================
int coinChangeBU(int sum, vector<int> coins){
    int n=coins.size();
    vector< vector<int> > dp(sum+1, vector<int> (n+1) );
    // base cases
    for(int amount=1; amount<=sum; amount++){
        dp[amount][0]=0; // no coins
    }
    for(int numCoins=0; numCoins<=n; numCoins++){
        dp[0][numCoins]=1; // one way to make change for 0
    }

    for(int amount=1; amount<=sum; amount++){
        for(int numCoins=1; numCoins<=n ; numCoins++){
            int with=0;
            // NOTE:
            // here numCoins is not index for coins array
            // for accessing coins arra index will be numCoins-1
            if(coins[numCoins-1] <= amount ){
                int remaining = amount - coins[numCoins-1];
                with = dp[remaining][numCoins];
            }
            int without= dp[amount][numCoins-1]; // upto prev num of coins
            dp[amount][numCoins]=with+without;
        }
    }
    cout<<"BottomUp Table:"<<endl;
    for(int i=0;i<=sum;i++){
        cout<<i<<" : ";
        for(int j=0;j<=n;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }
    return dp[sum][n];
}
int main(){
    freopen("ip.txt","r",stdin);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int> coins(n);
        for(int i=0;i<n;i++){
            cin>>coins[i];
        }
        int sum;
        cin>>sum;
        cout<<"Memoization Logic 1: "<<coinChange1(sum,coins)<<endl;
        cout<<"Memoization Logic 2:"<<coinChange2(sum,coins)<<endl;
        cout<<"TopDown: "<<coinChangeTD(sum,coins)<<endl;
        cout<<"BottomUp: "<<coinChangeBU(sum,coins)<<endl;
    }
}