Find minimum number of coins that make a given value when use one coin only one by recursion

#include<bits/stdc++.h>

#define INF 999999

using namespace std;

int c[50];                               /// maximum coin number

int num[50][100000];          /// number of coin count

int n;

int cnt(int i, int w)

{

    if(w < 0)

        return INF;

    if(i == n)

    {

        if(w == 0)

            return 0;

        return INF;

    }

    if(num[i][w] != -1)

        return num[i][w];

    int ans1 = 1 + cnt(i+1, w-c[i]);

    int ans2 = cnt(i+1, w);

    num[i][w] = min(ans1, ans2);

    return num[i][w];

}

int main()

{

    cout << "Enter Number of Coin :: ";

    cin >> n;

    cout << "Enter Coin :: ";

    for(int i=0; i<n; i++)

        cin >> c[i];

    int target;

    cout << "Enter Target Amount :: ";

    cin >> target;

    for(int i=0; i<=n; i++)

    {

        for(int j=0; j<=target; j++)

            num[i][j] = -1;

    }

    int r = cnt(0, target);

    if(r != INF)

        cout << "Minimum Number of Coin :: " << r << "\n";

    else

        cout << "Not Possible" << "\n";

    return 0;

}