# C++ recursive solution with comments (60ms)

• ``````class Solution {
public:
int currBestResult;

void solve(const vector<int>::iterator & begin, const vector<int>::iterator & end, int amount, int currCount)
{
// find a solution, update currBestResult if this is better
if(amount == 0) {
if(currBestResult == -1)
currBestResult = currCount;
else
currBestResult = min(currBestResult, currCount);
return;
}

// use up all coin types, no solution
if(begin == end) return;
// can't achiveve a solution better than currBestResult, no need to explore more
if(currBestResult != -1 && currBestResult <= amount / *begin + currCount) return;

int count, currAmount;
// start from the largest remaining coin first
for (auto it = begin; it != end; ++it) {
int coin = *it;
// use coin as much as possible, so that we can get a good solution early to save exploration
currAmount = amount % coin;
count = amount / coin;
while(currAmount < amount) {
// find solutions to fill currAmount with smaller coins
solve(it + 1, end, currAmount, count + currCount);
// scale back by one largest coin to extend currAmount to try solve again in the next iteration
currAmount += coin;
count--;
}
}
}

int coinChange(vector<int>& coins, int amount) {
currBestResult = -1;
sort (coins.begin(), coins.end(), greater<int>());
solve(coins.begin(), coins.end(), amount, 0);
return currBestResult;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.