//int numOfCoins = 0;
class Solution {
private:
int dfs(vector<int>& coins, int i , int balance) {
if (balance == 0) {
//cout << specificCoin << endl;
return 0;
}
if (balance != 0 && i < 0) {
cout << " return specific " << endl;
return -1;
}
int specificCoin = 0;
//int i = 0;
cout << " balance " << balance << " coin " << coins[i] << " numOfCoins " << specificCoin << endl;
if (coins[i] <= balance) {
specificCoin = balance/coins[i];
balance = balance - (coins[i] * specificCoin);
cout << " Inside balance " << balance << " coin " << coins[i] << " specificCoin " << specificCoin << endl;
}
cout << " specific " << specificCoin << endl;
if (balance != 0 && (i-1 < 0)) {
cout << " 2 specific " << specificCoin << endl;
specificCoin = 0;
}
specificCoin += dfs(coins, i-1, balance);
cout << "DFS is done " << specificCoin << endl;
return specificCoin;
}
public:
int coinChange(vector<int>& coins, int amount) {
if (amount < 0 || coins.size() < 1 || coins.size() > 12) {
return -1;
}
for (int i = coins.size() -1; i >= 0; i--) {
if (coins[i] < 1 || coins[i] > 2147483647) {
return -1;
}
}
int balance = amount;
int numOfCoins = 0, specificCoin = 0, minCoins = 0;
sort(coins.begin(), coins.end());
for (int i = 0; i< coins.size(); i++) {
numOfCoins = balance/coins[i];
specificCoin = balance/coins[i];
balance = balance - (coins[i] * specificCoin);
numOfCoins += dfs(coins, (coins.size() -1), balance);
if (minCoins > numOfCoins) {
minCoins = numOfCoins;
}
numOfCoins = 0;
}
return minCoins;
}
};
#if 0
Testcases
[1, 2, 5]
27
[2, 5, 10, 1]
11
//return -1 for balance != 0
[2]
3
// if not sorted
[2, 5, 10, 1]
27
#endif
