• When the input is [186,419,83,408] 6249, the answer is 26 rather than the correct one 20 .

The coins given by my solution are:
83 83 83 83 83 83 83 83 83 83 83 83 83 186 408 408 408 408 419 419 419 419 419 419 419 419.

What's problem with my solution, can any one give some advice, thanks very much!

``````  class Solution {
public:
bool cal(vector<int> &coins, int start, int end, int amount, vector<int> &res){
if(amount == 0) return true;
if(amount < 0) return false;
bool ret = false;
for(int i = start; i <= end; i++){
ret = cal(coins, i, end, amount - coins[i], res);
if(ret){
res.push_back(coins[i]);
break;
}
}

return ret;
}

int coinChange(vector<int>& coins, int amount) {
if(amount < 0) return -1;
if(amount == 0) return 0;

vector<int> res;
sort(coins.begin(), coins.end());
reverse(coins.begin(), coins.end());
bool ret = cal(coins, 0, coins.size() - 1, amount, res);

if(ret) return res.size();

return -1;
}
};``````

• Have yourself noticed that your program will stop at once it find a reasonable(but not necessary optimal) solution? That's the reason why it doesn't work correctly...

• Yes, i got it, the greedy algorithm doesn't work as expected. Thank you very much!

• Exactly where I was wrong, Thanks.

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