Why this backtracking algorithm doesn't work? Please help me,thanks very much!!


  • 1
    M

    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;
            }
        };

  • 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...


  • 0
    M

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


  • 0
    A

    Exactly where I was wrong, Thanks.


Log in to reply
 

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