LeetCode 1774 - Closest Dessert Cost

The problem asks us to create a dessert using one ice cream base and zero or more toppings, with the additional restriction that each topping type can be used at most twice.

leetcodemediumarraydynamic-programmingbacktracking

LeetCode Problem 1774

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Backtracking

Solution

Problem Understanding

The problem asks us to create a dessert using one ice cream base and zero or more toppings, with the additional restriction that each topping type can be used at most twice. Each base and topping has a cost, and our goal is to make a dessert whose total cost is as close as possible to a given target value. If multiple combinations produce costs equally close to the target, we should return the smaller one.

The inputs are two integer arrays, baseCosts and toppingCosts, and an integer target. Each element in baseCosts represents the cost of one ice cream base, while each element in toppingCosts represents the cost of a single unit of a topping type. The constraints tell us that both arrays have lengths at most 10, and all costs and the target are reasonably bounded (1 to 10^4). The small input sizes indicate that an exhaustive search could be feasible, but we still need an efficient approach because each topping can appear 0, 1, or 2 times, leading to up to 3^m topping combinations for each base.

Edge cases include scenarios where the target is smaller than all base costs, where the target exactly matches a base cost, or where multiple combinations yield the same minimum distance to the target. The algorithm must handle these gracefully by choosing the smaller cost if there is a tie.

Approaches

The brute-force approach is to generate all possible desserts by iterating over every base and considering all combinations of 0, 1, or 2 of each topping. For each combination, we calculate the total cost and keep track of the closest cost to the target. This is correct because it considers all valid desserts, but the complexity grows as O(n * 3^m), which is acceptable for n, m ≤ 10 but may be unnecessary given the small problem size.

The optimized approach uses a backtracking (DFS) strategy. We iterate over each base, then recursively explore adding 0, 1, or 2 of each topping, updating the closest cost whenever we find a combination closer to the target. The recursion ensures that all valid combinations are considered without explicitly storing all possibilities in memory. This method avoids unnecessary computation by pruning paths that cannot improve the solution, particularly when the current total already exceeds the target and adding more toppings can only make it worse.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * 3^m) O(1) Generates all combinations of toppings for each base explicitly
Backtracking / DFS O(n * 3^m) O(m) Recursively explores toppings, updates closest cost dynamically

Algorithm Walkthrough

  1. Initialize a variable closest to track the closest cost to the target, starting with any base cost.
  2. Define a recursive helper function dfs(index, currentCost) where index represents the topping being considered and currentCost is the total dessert cost so far.
  3. At each topping, recursively call dfs for three cases: using 0, 1, or 2 units of that topping. Add the corresponding topping cost to currentCost.
  4. In each recursive call, update closest if currentCost is closer to the target than the current closest. If two costs are equally close, prefer the smaller one.
  5. Start the DFS for each base cost in baseCosts with index = 0 and currentCost = base.
  6. Return closest after exploring all combinations.

Why it works: The DFS explores all valid topping combinations for each base while dynamically updating the closest cost. The invariant is that after visiting all recursive paths, closest holds the minimum difference to the target. Since all paths are considered, it guarantees correctness.

Python Solution

from typing import List

class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        closest = min(baseCosts, key=lambda x: (abs(x - target), x))
        
        def dfs(index: int, currentCost: int):
            nonlocal closest
            if abs(currentCost - target) < abs(closest - target) or \
               (abs(currentCost - target) == abs(closest - target) and currentCost < closest):
                closest = currentCost
            if index == len(toppingCosts):
                return
            for count in range(3):
                dfs(index + 1, currentCost + toppingCosts[index] * count)
        
        for base in baseCosts:
            dfs(0, base)
        return closest

The Python implementation initializes closest with the base cost closest to the target as a starting point. The recursive DFS considers 0, 1, or 2 of each topping and updates closest when a better option is found. The use of nonlocal allows the recursive function to modify closest in the outer scope.

Go Solution

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

    var dfs func(int, int)
    dfs = func(index int, currentCost int) {
        if absDiff(currentCost, target) < absDiff(closest, target) || 
           (absDiff(currentCost, target) == absDiff(closest, target) && currentCost < closest) {
            closest = currentCost
        }
        if index == len(toppingCosts) {
            return
        }
        for count := 0; count <= 2; count++ {
            dfs(index+1, currentCost + toppingCosts[index]*count)
        }
    }

    for _, base := range baseCosts {
        dfs(0, base)
    }
    return closest
}

func absDiff(a, b int) int {
    if a > b {
        return a - b
    }
    return b - a
}

The Go implementation mirrors the Python version, using a closure for DFS. It also uses a helper function absDiff to calculate absolute differences cleanly. Since Go does not have nonlocal, the closure captures closest by reference.

Worked Examples

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

Base Toppings Total Cost Closest Update
1 3+3=6 7 7
1 3+0=3 4 7
7 3+0=3 10 10

Return 10.

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

Base Toppings Total Cost Closest Update
3 4+10 17 17
3 4+0 7 17
2 4+10 16 17

Return 17.

Example 3: baseCosts = [3,10], toppingCosts = [2,5], target = 9

Base Toppings Total Cost Closest Update
3 2+2=4 7 8
3 2+5=7 10 8
10 0+0=0 10 8

Return 8.

Complexity Analysis

Measure Complexity Explanation
Time O(n * 3^m) Each base triggers a DFS exploring 3 choices per topping, so total is n * 3^m
Space O(m) Maximum recursion depth is the number of toppings, m

The time complexity is acceptable given n, m ≤ 10. Space complexity is limited to recursion stack depth.

Test Cases

# Provided examples
assert Solution().closestCost([1,7], [3,4], 10) == 10  # exact match
assert Solution().closestCost([2,3], [4,5,100], 18) == 17  # closest under target
assert Solution().closestCost([3,10], [2,5], 9) == 8  # tie, return smaller

# Edge cases
assert Solution().closestCost([5], [], 4) == 5  # only base, no toppings
assert Solution().closestCost([1,2,3], [1], 100) == 3 + 1*2  # max toppings used
assert Solution().closestCost([10], [1,1,1,1,1,1,1,1,1,1], 15) == 15  # many toppings
Test Why
exact match Ensures algorithm returns correct exact target
closest under target Ensures algorithm handles best under-target scenario
tie, return smaller Confirms tie-breaking logic
only base Handles