Krammer's blog

https://leetcode.com/problems/closest-dessert-cost/ from Google

Thinking process:

From the problem statement, there must be exactly one ice cream base. The number of base is at most 10, so we can just try these 10 possibilies. In terms of the toppings, we can basically use a DP way to generate all possible costs.

Here is the code.

 1class Solution {
 2public:
 3    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
 4        int N = baseCosts.size();
 5        int M = toppingCosts.size();
 6        unordered_set<int> s;
 7        s.insert(0);
 8        for (int i=0; i<M; i++) {
 9            unordered_set<int> ns;
10            for (auto n : s) {
11                ns.insert(n + toppingCosts[i]);
12                ns.insert(n + 2*toppingCosts[i]);
13            }
14            for (auto n : ns) {
15                s.insert(n);
16            }
17        }
18        int ans = INT_MAX;
19        for (int i=0; i<N; i++) {
20            for (auto n : s) {
21                int cost = (baseCosts[i] + n);
22                if (abs(cost - target) < abs(ans - target) or 
23                   (abs(cost - target) == abs(ans - target) and cost < ans))
24                    ans = cost;
25            }
26        }
27        return ans;
28    }
29};

Editorial: LeetCode 1774 Closest Dessert Cost