1900-closest-dessert-cost.cpp

class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts,
                    int target) {
        int closest = INT_MAX;
        for (auto c : baseCosts) {
            stack<pair<int,int>> states;
            states.push({0,c});
            while (!states.empty()) {
                auto s = states.top();
                states.pop();
                // check solution
                if (s.second == target) return target;
                if (abs(s.second-target) < abs(closest-target)) {
                    closest = s.second;
                }
                if (abs(s.second-target) == abs(closest-target) && (s.second < closest)) {
                    closest = s.second;
                }
                if (s.first == toppingCosts.size()) continue;

                // push children
                for (int i=0;i<3;i++) {
                    states.push({s.first+1, s.second + i*toppingCosts[s.first]});
                }
            }
        }
        return closest;
    }
};