Closest Dessert Cost

medium array backtracking enumeration

Problem

Build a dessert by choosing exactly one ice cream base from baseCosts and adding toppings from toppingCosts, where each topping may be used 0, 1, or 2 times. Return the total cost closest to target; if two totals are equally close, return the lower one.

InputbaseCosts = [1,7], toppingCosts = [3,4], target = 10

Output10

Base 7 + one of topping 3 + zero of topping 4 = 10, exactly the target.

baseCosts (comma-separated)

toppingCosts (comma-separated)

target

def closestCost(baseCosts, toppingCosts, target):
    best = baseCosts[0]                      # any valid dessert; refined below

    def consider(total):
        nonlocal best
        # closer to target wins; on a tie keep the lower total
        if abs(total - target) < abs(best - target) or \
           (abs(total - target) == abs(best - target) and total < best):
            best = total

    def dfs(i, total):
        if i == len(toppingCosts):
            consider(total)                  # a complete dessert
            return
        for k in range(3):                   # use 0, 1, or 2 of topping i
            dfs(i + 1, total + k * toppingCosts[i])

    for b in baseCosts:                      # exactly one base each time
        dfs(0, b)
    return best

function closestCost(baseCosts, toppingCosts, target) {
  let best = baseCosts[0];                     // any valid dessert; refined below

  function consider(total) {
    // closer to target wins; on a tie keep the lower total
    if (Math.abs(total - target) < Math.abs(best - target) ||
        (Math.abs(total - target) === Math.abs(best - target) && total < best)) {
      best = total;
    }
  }

  function dfs(i, total) {
    if (i === toppingCosts.length) {
      consider(total);                         // a complete dessert
      return;
    }
    for (let k = 0; k < 3; k++) {              // use 0, 1, or 2 of topping i
      dfs(i + 1, total + k * toppingCosts[i]);
    }
  }

  for (const b of baseCosts) {                 // exactly one base each time
    dfs(0, b);
  }
  return best;
}

int best;

int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
    best = baseCosts[0];                       // any valid dessert; refined below
    for (int b : baseCosts) {                  // exactly one base each time
        dfs(toppingCosts, target, 0, b);
    }
    return best;
}

void dfs(int[] toppingCosts, int target, int i, int total) {
    if (i == toppingCosts.length) {            // a complete dessert
        if (Math.abs(total - target) < Math.abs(best - target) ||
            (Math.abs(total - target) == Math.abs(best - target) && total < best)) {
            best = total;                      // closer, or tie -> lower
        }
        return;
    }
    for (int k = 0; k < 3; k++) {              // use 0, 1, or 2 of topping i
        dfs(toppingCosts, target, i + 1, total + k * toppingCosts[i]);
    }
}

int best;

void dfs(vector<int>& toppingCosts, int target, int i, int total) {
    if (i == (int)toppingCosts.size()) {       // a complete dessert
        if (abs(total - target) < abs(best - target) ||
            (abs(total - target) == abs(best - target) && total < best)) {
            best = total;                      // closer, or tie -> lower
        }
        return;
    }
    for (int k = 0; k < 3; k++) {              // use 0, 1, or 2 of topping i
        dfs(toppingCosts, target, i + 1, total + k * toppingCosts[i]);
    }
}

int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
    best = baseCosts[0];                        // any valid dessert; refined below
    for (int b : baseCosts) {                   // exactly one base each time
        dfs(toppingCosts, target, 0, b);
    }
    return best;
}

Explanation

The constraints are tiny (at most 10 bases and 10 toppings), so we simply enumerate every legal dessert and keep the one closest to target. This is classic backtracking: each topping branches three ways.

For a fixed base, the recursion dfs(i, total) decides topping i by trying 0, 1, or 2 of it and adding k · toppingCosts[i] to the running total, then recursing on the next topping. When i reaches the end of the toppings, total is a complete dessert cost.

Every complete dessert is fed to consider, which updates best using the tie rule: a smaller distance |total − target| always wins, and when two distances are equal we keep the lower total. We seed best with a valid dessert (baseCosts[0] with no toppings) so the comparison is always well defined.

We repeat the whole search once per base, because the dessert must contain exactly one base. The answer is the best total found across all bases and all topping choices.

Example: with baseCosts = [1,7], toppingCosts = [3,4], target = 10, the combination 7 + 1·3 + 0·4 = 10 hits the target exactly, so the answer is 10.

Time: O(n · 3^m) Space: O(m)