Minimum Coin Required By Recursion

#include<bits/stdc++.h>
#define speed ios_base :: sync_with_stdio(false);cin.tie(NULL)
using namespace std;
bool compare(int A, int B)
{
    return (A > B);
}
int coin(vector<int>v, int t)
{
    if(t == 0)
        return 0;
    int result = INT_MAX;
    for(int i=0;i<v.size();i++)
    {
        if(v[i] <= t)
        {
            int sub_result = coin(v, t-v[i]);
            if(sub_result != INT_MAX && sub_result + 1 < result)
                result = sub_result + 1;
        }
    }
    return result;
}
int main()
{
    int n, i, tm;

    cout << "Enter Total Coin Number :: ";
    cin >> n;

    vector<int>v(n);

    cout << "Enter Coins Amount :: " << "\n";
    for(i=0;i<n;i++)
        cin >> v[i];

    cout << "Enter Total Amount :: ";
    cin >> tm;

    sort(v.begin(),v.end(), compare);

    cout << "Minimum Coin Required :: " << coin(v, tm) << "\n";

    return 0;
}

Comments