Closest Dessert Cost

LeetCode problem #1774

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

You are given:

  • baseCosts: costs of different base ice creams (choose exactly one base)
  • toppingCosts: costs of different toppings (for each topping, you may choose 0, 1, or 2 of it)
  • target: desired total cost

Return the total cost of a dessert that is closest to target.

Tie-breaker:

  • If two totals are equally close to target, return the smaller total.

Input / Output Format

Input

  • baseCosts: integer array
  • toppingCosts: integer array
  • target: integer

Output

  • integer: closest achievable total cost

Constraints (LeetCode #1774)

  • 1 <= baseCosts.length <= 10
  • 1 <= toppingCosts.length <= 10
  • 1 <= baseCosts[i], toppingCosts[i] <= 10^4
  • 1 <= target <= 10^4

Examples

Example 1

Input

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

Explanation Possible totals:

  • Base 7 + topping 3 = 10 (exact) Return 10.

Example 2

Input

  • baseCosts = [2,3]
  • toppingCosts = [4,5,100]
  • target = 18

Explanation Try combinations (0/1/2 of each topping). One close option:

  • Base 3 + 5 + 5 + 4 = 17 (distance 1) Other nearby totals might be 18? Not achievable here; so return 17.

Example 3 (Tie-breaker)

Input

  • baseCosts = [3]
  • toppingCosts = [2]
  • target = 4

Explanation Possible totals:

  • 3 (diff 1)
  • 5 (3 + 2, diff 1) Both are equally close; return smaller => 3.

Edge Example (Already above target)

Input

  • baseCosts = [10]
  • toppingCosts = [1]
  • target = 1

Explanation You must pick one base, so minimum total is 10. Return 10.

Approach 1: Brute Force

Idea

Enumerate all topping selections (each topping has 3 choices: 0, 1, 2), compute every possible topping sum, then combine with each base cost and pick the best total by:

  1. minimal abs(total - target)
  2. if tie, minimal total

Since toppingCosts.length <= 10, total topping combinations are 3^10 = 59049, which is manageable.

Algorithm

  1. Generate all possible topping sums via DFS/backtracking:
    • For topping i, branch into adding 0, 1*topping[i], 2*topping[i]
  2. For each base b and each topping sum s, evaluate total b + s.
  3. Track the best total using the tie-breaking rule.

Python Implementation (Brute Force)

from typing import List

class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        topping_sums = []

        def dfs(i: int, curr: int) -> None:
            if i == len(toppingCosts):
                topping_sums.append(curr)
                return
            cost = toppingCosts[i]
            dfs(i + 1, curr)           # 0 of this topping
            dfs(i + 1, curr + cost)    # 1 of this topping
            dfs(i + 1, curr + 2 * cost)# 2 of this topping

        dfs(0, 0)

        best = None
        best_diff = float("inf")

        for b in baseCosts:
            for s in topping_sums:
                total = b + s
                diff = abs(total - target)
                if diff < best_diff or (diff == best_diff and (best is None or total < best)):
                    best_diff = diff
                    best = total

        return best

Complexity

  • Number of topping sums: 3^m where m = len(toppingCosts) <= 10
  • Time: O(3^m * n) where n = len(baseCosts) <= 10 → at most ~590k evaluations
  • Space: O(3^m) to store topping sums

Approach 2: Optimized Solution (Pruning DFS)

When/Why Optimize?

Brute force is already fine for constraints, but in interviews you can show pruning to reduce work and demonstrate search optimization.

Key Optimization

Instead of generating all topping sums first, do DFS per base and prune:

  • Maintain a global best answer.
  • If current cost is already above target, adding more toppings only increases cost. However, you might still need to consider “slightly above” costs because they could be closest.
    So we can prune when curr - target is already worse than current best difference and all future additions are non-negative (they are).

Algorithm

  1. Initialize best as the minimum base cost (or any base).
  2. For each base b, DFS over toppings:
    • At each node, update best with curr.
    • If curr > target and curr - target > abs(best - target) then prune (cannot improve by adding more).
    • Recurse with choices +0, +t, +2t.

This keeps correctness and often explores far fewer nodes.

Python (Optimized DFS)

from typing import List

class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        best = min(baseCosts)

        def better(x: int, y: int) -> int:
            # return the better of x and y according to problem rules
            dx, dy = abs(x - target), abs(y - target)
            if dx != dy:
                return x if dx < dy else y
            return x if x < y else y

        def dfs(i: int, curr: int) -> None:
            nonlocal best
            best = better(best, curr)

            # Prune: if we're already above target and worse than best, adding more won't help
            if curr > target and curr - target > abs(best - target):
                return

            if i == len(toppingCosts):
                return

            t = toppingCosts[i]
            dfs(i + 1, curr)         # 0
            dfs(i + 1, curr + t)     # 1
            dfs(i + 1, curr + 2 * t) # 2

        for b in baseCosts:
            dfs(0, b)

        return best

Java (Optimized DFS)

import java.util.*;

class Solution {
    private int target;
    private int best;
    private int[] topping;

    private int better(int a, int b) {
        int da = Math.abs(a - target), db = Math.abs(b - target);
        if (da != db) return da < db ? a : b;
        return Math.min(a, b);
    }

    private void dfs(int i, int curr) {
        best = better(best, curr);

        if (curr > target && curr - target > Math.abs(best - target)) return;
        if (i == topping.length) return;

        int t = topping[i];
        dfs(i + 1, curr);
        dfs(i + 1, curr + t);
        dfs(i + 1, curr + 2 * t);
    }

    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        this.target = target;
        this.topping = toppingCosts;
        best = baseCosts[0];
        for (int b : baseCosts) best = Math.min(best, b);

        for (int b : baseCosts) dfs(0, b);
        return best;
    }
}

Go (Optimized DFS)

package main

import "math"

func closestCost(baseCosts []int, toppingCosts []int, target int) int {
	best := baseCosts[0]
	for _, b := range baseCosts {
		if b < best {
			best = b
		}
	}

	better := func(a, b int) int {
		da := int(math.Abs(float64(a - target)))
		db := int(math.Abs(float64(b - target)))
		if da != db {
			if da < db {
				return a
			}
			return b
		}
		if a < b {
			return a
		}
		return b
	}

	var dfs func(i int, curr int)
	dfs = func(i int, curr int) {
		best = better(best, curr)

		if curr > target && curr-target > int(math.Abs(float64(best-target))) {
			return
		}
		if i == len(toppingCosts) {
			return
		}
		t := toppingCosts[i]
		dfs(i+1, curr)
		dfs(i+1, curr+t)
		dfs(i+1, curr+2*t)
	}

	for _, b := range baseCosts {
		dfs(0, b)
	}
	return best
}

JavaScript (Optimized DFS)

var closestCost = function(baseCosts, toppingCosts, target) {
  let best = Math.min(...baseCosts);

  function better(a, b) {
    const da = Math.abs(a - target), db = Math.abs(b - target);
    if (da !== db) return da < db ? a : b;
    return Math.min(a, b);
  }

  function dfs(i, curr) {
    best = better(best, curr);

    if (curr > target && (curr - target) > Math.abs(best - target)) return;
    if (i === toppingCosts.length) return;

    const t = toppingCosts[i];
    dfs(i + 1, curr);
    dfs(i + 1, curr + t);
    dfs(i + 1, curr + 2 * t);
  }

  for (const b of baseCosts) dfs(0, b);
  return best;
};

C# (Optimized DFS)

using System;

public class Solution {
    private int target;
    private int best;
    private int[] topping;

    private int Better(int a, int b) {
        int da = Math.Abs(a - target), db = Math.Abs(b - target);
        if (da != db) return da < db ? a : b;
        return Math.Min(a, b);
    }

    private void Dfs(int i, int curr) {
        best = Better(best, curr);

        if (curr > target && curr - target > Math.Abs(best - target)) return;
        if (i == topping.Length) return;

        int t = topping[i];
        Dfs(i + 1, curr);
        Dfs(i + 1, curr + t);
        Dfs(i + 1, curr + 2 * t);
    }

    public int ClosestCost(int[] baseCosts, int[] toppingCosts, int target) {
        this.target = target;
        this.topping = toppingCosts;

        best = baseCosts[0];
        foreach (var b in baseCosts) best = Math.Min(best, b);

        foreach (var b in baseCosts) Dfs(0, b);
        return best;
    }
}

Complexity

Worst-case remains:

  • Time: O(n * 3^m)
  • Space: O(m) recursion depth (no need to store all sums) In practice, pruning often reduces explored states.

Key Insights

  • Each topping has three discrete choices: {0, 1, 2} → classic DFS/backtracking with branching factor 3.
  • Constraints are small (m <= 10), making 3^m feasible.
  • The tie-breaker (“if equally close, choose smaller”) must be enforced everywhere you compare candidates.
  • Pruning works because topping costs are non-negative: once you overshoot target by more than the best known difference, adding more can’t improve closeness.

Edge Cases

  • Exact match exists (return target).
  • All bases already exceed target; must still pick one base (answer is smallest base or best by closeness if toppings can’t reduce).
  • Tie in distance: e.g., totals target-1 and target+1 → return target-1.
  • toppingCosts empty (not per constraints here, but good to handle conceptually): answer is closest base.
  • Large topping values where only 0 helps; ensure DFS still considers “skip topping” path.
  • Multiple bases; best may come from a non-min base due to topping combinations.

Test Cases (Python)

import unittest

class TestClosestDessertCost(unittest.TestCase):
    def test_example1(self):
        from typing import List
        class Solution:
            def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
                best = min(baseCosts)

                def better(x: int, y: int) -> int:
                    dx, dy = abs(x - target), abs(y - target)
                    if dx != dy:
                        return x if dx < dy else y
                    return x if x < y else y

                def dfs(i: int, curr: int) -> None:
                    nonlocal best
                    best = better(best, curr)
                    if curr > target and curr - target > abs(best - target):
                        return
                    if i == len(toppingCosts):
                        return
                    t = toppingCosts[i]
                    dfs(i + 1, curr)
                    dfs(i + 1, curr + t)
                    dfs(i + 1, curr + 2 * t)

                for b in baseCosts:
                    dfs(0, b)
                return best

        self.assertEqual(Solution().closestCost([1,7], [3,4], 10), 10)

    def test_tie_break(self):
        # base 3, topping 2, target 4: totals 3 and 5 both diff 1 => return 3
        from typing import List
        class Solution:
            def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
                best = min(baseCosts)
                def better(a, b):
                    da, db = abs(a-target), abs(b-target)
                    if da != db: return a if da < db else b
                    return a if a < b else b
                def dfs(i, curr):
                    nonlocal best
                    best = better(best, curr)
                    if curr > target and curr - target > abs(best - target): return
                    if i == len(toppingCosts): return
                    t = toppingCosts[i]
                    dfs(i+1, curr)
                    dfs(i+1, curr+t)
                    dfs(i+1, curr+2*t)
                for b in baseCosts: dfs(0, b)
                return best
        self.assertEqual(Solution().closestCost([3], [2], 4), 3)

    def test_all_bases_above_target(self):
        from typing import List
        class Solution:
            def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
                best = min(baseCosts)
                def better(a, b):
                    da, db = abs(a-target), abs(b-target)
                    if da != db: return a if da < db else b
                    return a if a < b else b
                def dfs(i, curr):
                    nonlocal best
                    best = better(best, curr)
                    if curr > target and curr - target > abs(best - target): return
                    if i == len(toppingCosts): return
                    t = toppingCosts[i]
                    dfs(i+1, curr)
                    dfs(i+1, curr+t)
                    dfs(i+1, curr+2*t)
                for b in baseCosts: dfs(0, b)
                return best
        self.assertEqual(Solution().closestCost([10], [1], 1), 10)

    def test_exact_with_double_topping(self):
        # base 5 + 2*3 = 11
        from typing import List
        class Solution:
            def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
                best = min(baseCosts)
                def better(a, b):
                    da, db = abs(a-target), abs(b-target)
                    if da != db: return a if da < db else b
                    return a if a < b else b
                def dfs(i, curr):
                    nonlocal best
                    best = better(best, curr)
                    if curr > target and curr - target > abs(best - target): return
                    if i == len(toppingCosts): return
                    t = toppingCosts[i]
                    dfs(i+1, curr)
                    dfs(i+1, curr+t)
                    dfs(i+1, curr+2*t)
                for b in baseCosts: dfs(0, b)
                return best
        self.assertEqual(Solution().closestCost([5], [3], 11), 11)

if __name__ == "__main__":
    unittest.main()

Common Mistakes

  • Forgetting the tie-breaker: when distances are equal, must return the smaller total.
  • Accidentally allowing “no base chosen” (you must pick exactly one base).
  • Not exploring the “0 topping” choice for each topping.
  • Using pruning that is too aggressive (e.g., pruning immediately when curr > target without comparing against best).
  • Integer overflow concerns in some languages (less likely here, but still keep totals in int/long appropriately).

Interview Tips

  • Start by restating: “One base, each topping 0/1/2, minimize absolute difference, tie to smaller.”
  • Call out the key observation: m <= 10 so 3^m is feasible; propose DFS/backtracking.
  • Explain tie-break logic as a helper better(a,b) comparator.
  • If asked to optimize, introduce pruning based on current best difference once you exceed target.
  • Discuss complexity confidently: worst-case O(n * 3^m) and why that’s acceptable under constraints.
  • Mention alternative viewpoint: generate all topping sums first (meet-in-the-middle is possible, but unnecessary here).