Find minimum number of coins that make a given value when use one coin many times

#include<bits/stdc++.h>

#define N 100000

#define INF 9999999

using namespace std;

int c[50];

int num[N];

int n;

int cnt(int w)

{

    if(w < 0)

        return INF;

    if(w == 0)

        return 0;

    if(num[w] == -1)

        return num[w];

    int ans = INF;

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

        ans = min(ans, 1+cnt(w-c[i]));

    num[w] = ans;

    return num[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;

    int r = cnt(target);

    if(r != INF)

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

    else

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

    return 0;

}