322. Coin Change

class Solution { public: void coinHelper(vector<int> & coins, int amount, int chosen, int max, int & count, vector<int> & res){ if (count > max) return; else if (chosen == amount ){ res.push_back(count); return; } for (auto c: coins){ // choose chosen += c; count++; // explore coinHelper(coins, amount, chosen, max, count, res); // unchoose count--; chosen -= c; } } int coinChange(vector<int>& coins, int amount) { vector<int> res; // store all counts int count = 0; int chosen = 0; int mincoin = coins.front(); for (auto c: coins){ if(c < mincoin) mincoin = c; } int max = amount / mincoin + 1; // the maximum number of coins. To prevent infinite loop. // call helper to populate res... coinHelper(coins, amount, chosen, max, count, res); if (res.empty()) return -1; int mincount = res.front(); for (auto c: res){ if (c < mincount) mincount = c; } return mincount; } };