C++ recursive solution with comments (60ms)


  • 0
    T
    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;
        }
    };

Log in to reply
 

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