1774. Closest Dessert Cost

You would like to make dessert and are preparing to buy the ingredients. You have n ice cream base flavors and m types of toppings to choose from. You must follow these rules when making your dessert:

• There must be exactly one ice cream base.
• You can add one or more types of topping or have no toppings at all.
• There are at most two of each type of topping.

You are given three inputs:

• baseCosts, an integer array of length n, where each baseCosts[i] represents the price of the ith ice cream base flavor.
• toppingCosts, an integer array of length m, where each toppingCosts[i] is the price of one of the ith topping.
• target, an integer representing your target price for dessert.

You want to make a dessert with a total cost as close to target as possible.

Return the closest possible cost of the dessert to target. If there are multiple, return the lower one.

class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        set<int> toppingCost;
        toppingCost.insert(0);
        for(auto& toppings : toppingCosts) {
            unordered_set<int> topping;
            for(auto& cost : toppingCost) {
                topping.insert(cost + toppings);
                topping.insert(cost + 2 * toppings);
            }

            for(auto& myTopping : topping) {
                toppingCost.insert(myTopping);
            }
        }
        int res = baseCosts[0];
        for(auto& base : baseCosts) {
            int cost = base;
            auto choose = lower_bound(begin(toppingCost), end(toppingCost), target - base);
            if(choose == end(toppingCost)) {
                cost += *prev(choose);
            } else if(choose == begin(toppingCost)){
                cost += *choose;
            } else {
                auto prevChoose = prev(choose);
                if(abs(target - (cost + *prevChoose)) <= abs(target - (cost + *choose))) {
                    cost += *prevChoose;
                } else {
                    cost += *choose;
                }
            }
            if(abs(target - res) > abs(target - cost)){
                res = cost;
            } else if(abs(target - res) == abs(target - cost)) {
                res = min(res, cost);
            }
        }

        return res;
    }
};