Share my 28ms c++ solution


  • -1
    S
    class Solution{
    public:
            int coinChange(vector<int>& coins,int amount){
                 if(amount==0)return 0;
                 if(coins.size()==0)return -1;
                 sort(coins.begin(),coins.end());
                 int tmpcount=amount/coins[0]+1;
                 tmpcount=helper(coins,amount,tmpcount);
                 if(tmpcount>amount/coins[0])return -1;
                 else return tmpcount;
            }
            int helper(vector<int>& coins,int amount,int tmpcount){
                 if(amount==0)return 0;
                 int largest=coins.back();
                 if(tmpcount*largest<amount)return -1;
                 for(int k=amount/largest;k>=0;k--){
                         coins.pop_back();
                         int tmp=helper(coins,amount-k*largest,tmpcount-k);
                         if(tmp!=-1)tmpcount=tmp+k;
                         coins.push_back(largest);
                 }
                 return tmpcount;
            }
    };

Log in to reply
 

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