3ms c++, easy to understand!


  • 0
    C
    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            int res = INT_MAX;
            sort(coins.begin(), coins.end());
            dfs(res, coins, amount, coins.size() - 1, 0);
            return res == INT_MAX? -1: res;
        }
        void dfs(int& res, vector<int>& coins, int target, int idx, int count) {
            if (idx < 0) return;
            if (target % coins[idx] == 0) {
                res = min(res, count + target / coins[idx]);
                return;
            }
            for (int i = target / coins[idx]; i >= 0; i--) {
                if (count + i >= res - 1) break; // pruing
                dfs(res, coins, target - i * coins[idx], idx - 1, count + i);
            }
        }
    };

Log in to reply
 

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