#include <bits/stdc++.h>

using namespace std;
const int N = 100;
int dp[N];
vector<vector<int>>combinations[N];

void findCombinations(int amount,vector<int>&coins,vector<int>currentCombination)
{
    if(amount==0)
    {
        combinations[amount].push_back(currentCombination);
        return;
    }
    for(int coin:coins)
    {
        if(amount-coin>=0)
        {
            currentCombination.push_back(coin);
            findCombinations(amount-coin,coins,currentCombination);
            currentCombination.pop_back();
        }
    }
}
void print_combinations(int amount)
{
    if(combinations[amount].empty())
    {
        cout<<"No combinations found"<<endl;
        return;
    }
    cout<<"Combinations:"<< endl;
    for(vector<int>combination:combinations[amount])
    {
        for(int i=0;i<combination.size();i++)
        {
            cout << combination[i];
            if(i<combination.size() - 1)
                cout<< " + ";
        }
        cout<<endl;
    }
}
int func(int amount, vector<int>&coins)
{
    if(amount==0)
        return 0;
    int ans = INT_MAX;
    if(dp[amount]!=-1)
        return dp[amount];
    for(int coin : coins)
    {
        if((amount - coin) >= 0)
        {
            ans = min(ans+0LL, func(amount-coin,coins)+1LL);
        }
    }
    return dp[amount]=ans;
}
int choose_coin(vector<int>&coins, int amount)
{
    //memset(dp,-1,sizeof(dp));
    int ans = func(amount,coins);
    return ans == INT_MAX?-1:ans;
}

int main()
{
    //memset(dp,-1,sizeof(dp));
    vector<int>coins={2,3,4,5,6,9,15};
    cout<<"Minimum coin = "<<choose_coin(coins,23);
    findCombinations(23,coins,{});
    print_combinations(23);
    //for(int i=0;i<sizeof(dp);i++)
    //{
    //    cout<<dp[i]<<" ";
    //}
    return 0;
}