Problem Description

You are given three inputs:

• baseCosts: An array of integers, where each element represents the cost of a different base dessert.
• toppingCosts: An array of integers, where each element represents the cost of a different topping type.
• target: An integer representing the target cost you want to achieve or get as close as possible to.

• Choosing exactly one base from baseCosts.
• Adding zero, one, or two of each type of topping from toppingCosts (i.e., for each topping, you can use it 0, 1, or 2 times).

• Each base can be chosen only once.
• Each topping type can be used at most twice.
• There is always at least one valid solution.

Thought Process

At first glance, the problem seems to suggest generating all possible combinations of bases and toppings, then picking the one closest to target. However, this brute-force approach could be inefficient, especially as the number of toppings increases (since each topping has three choices: 0, 1, or 2 times).

To optimize, we notice:

• The number of possible topping combinations is 3ⁿ where n is the number of toppings. For small n (≤10), this is manageable.
• For each base, we can try all topping combinations and track the closest total cost to target.
• We can use recursion (DFS/backtracking) to efficiently explore topping combinations for each base.
• Whenever we find a cost closer to target, or equally close but lower, we update our answer.

Solution Approach

We solve the problem using the following steps:

1. Iterate over all base costs: For each base, we treat it as the starting cost and attempt to add toppings in all possible combinations.
2. Use recursion (DFS) for toppings: For each topping, we have three choices: use it 0, 1, or 2 times. We recursively try each option, accumulating the total cost.
3. Track the best (closest) total: After each combination, check if the current total is closer to target than our best so far (or, if equally close, is lower). If so, update our answer.
4. Prune unnecessary paths: If the current total cost already exceeds a value much larger than target (optional), we can skip further recursion for efficiency.
5. Return the best answer found: After all bases and topping combinations have been tried, return the closest cost.

This approach is efficient because:

• There are only 3ⁿ topping combinations, which is feasible for n ≤ 10.
• We never repeat the same combination for a given base.
• We always keep track of the closest (and lowest, in case of ties) cost.

Example Walkthrough

Example Input:

• baseCosts = [1, 7]
• toppingCosts = [3, 4]
• target = 10

1. Try base = 1:
   • Try all topping combinations (each topping: 0, 1, or 2 times):
   • For example:
     • 0 of both: 1
     • 1 of 3, 0 of 4: 1+3=4
     • 2 of 3, 0 of 4: 1+6=7
     • 0 of 3, 1 of 4: 1+4=5
     • 1 of 3, 1 of 4: 1+3+4=8
     • 2 of 3, 1 of 4: 1+6+4=11
     • ... and so on for all combinations up to using 2 of each topping.
   • The possible totals for base=1: 1, 4, 5, 7, 8, 9, 11, 12.
2. Try base = 7:
   • Repeat the process, getting possible totals: 7, 10, 11, 13, 14, 15, etc.
3. Find which total is closest to 10. Possible candidates: 9, 10, 11, etc. 10 is exactly target, so we return 10.

This process ensures we check every valid combination and pick the best.

Time and Space Complexity

Brute-force approach:

• For each base (b), try every combination of toppings (3ⁿ for n toppings).
• Time complexity: O(b * 3ⁿ)
• Space complexity: O(1) if using simple recursion, or O(3ⁿ) if memoizing/computing all possible sums.

• We still check all combinations, but with pruning and early stopping, practical runtime is much better.
• For small n (≤10), this is acceptable.

The main factor is the number of toppings, since each can be used 0, 1, or 2 times, giving 3ⁿ combinations.

Summary

The Closest Dessert Cost problem is a classic combinatorial optimization challenge. By systematically trying all combinations of bases and toppings (using recursion or iteration), and always tracking the closest total to the target, we guarantee finding the best answer. The solution is made efficient by limiting the number of topping types and by using recursion to avoid unnecessary computations. The key insight is that with small input sizes, exploring all possible topping combinations is both feasible and effective.

Code Implementation

class Solution:
    def closestCost(self, baseCosts, toppingCosts, target):
        self.best = None

        def dfs(i, cost):
            # At each topping, decide 0, 1, or 2 times
            if i == len(toppingCosts):
                # Update best if this cost is closer (or equally close but lower)
                if (self.best is None or
                    abs(cost - target) < abs(self.best - target) or
                    (abs(cost - target) == abs(self.best - target) and cost < self.best)):
                    self.best = cost
                return
            # Try using this topping 0, 1, or 2 times
            for cnt in range(3):
                dfs(i + 1, cost + cnt * toppingCosts[i])

        for base in baseCosts:
            dfs(0, base)
        return self.best
      

class Solution {
public:
    int best;
    int target;

    void dfs(const vector<int>& toppingCosts, int i, int cost) {
        if (i == toppingCosts.size()) {
            if (best == -1 ||
                abs(cost - target) < abs(best - target) ||
                (abs(cost - target) == abs(best - target) && cost < best)) {
                best = cost;
            }
            return;
        }
        for (int cnt = 0; cnt <= 2; ++cnt) {
            dfs(toppingCosts, i + 1, cost + cnt * toppingCosts[i]);
        }
    }

    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        this->target = target;
        best = -1;
        for (int base : baseCosts) {
            dfs(toppingCosts, 0, base);
        }
        return best;
    }
};
      

class Solution {
    int best;
    int target;

    void dfs(int[] toppingCosts, int i, int cost) {
        if (i == toppingCosts.length) {
            if (best == -1 ||
                Math.abs(cost - target) < Math.abs(best - target) ||
                (Math.abs(cost - target) == Math.abs(best - target) && cost < best)) {
                best = cost;
            }
            return;
        }
        for (int cnt = 0; cnt <= 2; cnt++) {
            dfs(toppingCosts, i + 1, cost + cnt * toppingCosts[i]);
        }
    }

    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        this.target = target;
        best = -1;
        for (int base : baseCosts) {
            dfs(toppingCosts, 0, base);
        }
        return best;
    }
}
      

var closestCost = function(baseCosts, toppingCosts, target) {
    let best = null;

    function dfs(i, cost) {
        if (i === toppingCosts.length) {
            if (
                best === null ||
                Math.abs(cost - target) < Math.abs(best - target) ||
                (Math.abs(cost - target) === Math.abs(best - target) && cost < best)
            ) {
                best = cost;
            }
            return;
        }
        for (let cnt = 0; cnt <= 2; cnt++) {
            dfs(i + 1, cost + cnt * toppingCosts[i]);
        }
    }

    for (let base of baseCosts) {
        dfs(0, base);
    }
    return best;
};