Watch 10 video solutions for Closest Dessert Cost, a medium level problem involving Array, Dynamic Programming, Backtracking. This walkthrough by Cherry Coding [IIT-G] has 2,010 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You would like to make dessert and are preparing to buy the ingredients. You have n ice cream base flavors and m types of toppings to choose from. You must follow these rules when making your dessert:
You are given three inputs:
baseCosts, an integer array of length n, where each baseCosts[i] represents the price of the ith ice cream base flavor.toppingCosts, an integer array of length m, where each toppingCosts[i] is the price of one of the ith topping.target, an integer representing your target price for dessert.You want to make a dessert with a total cost as close to target as possible.
Return the closest possible cost of the dessert to target. If there are multiple, return the lower one.
Example 1:
Input: baseCosts = [1,7], toppingCosts = [3,4], target = 10 Output: 10 Explanation: Consider the following combination (all 0-indexed): - Choose base 1: cost 7 - Take 1 of topping 0: cost 1 x 3 = 3 - Take 0 of topping 1: cost 0 x 4 = 0 Total: 7 + 3 + 0 = 10.
Example 2:
Input: baseCosts = [2,3], toppingCosts = [4,5,100], target = 18 Output: 17 Explanation: Consider the following combination (all 0-indexed): - Choose base 1: cost 3 - Take 1 of topping 0: cost 1 x 4 = 4 - Take 2 of topping 1: cost 2 x 5 = 10 - Take 0 of topping 2: cost 0 x 100 = 0 Total: 3 + 4 + 10 + 0 = 17. You cannot make a dessert with a total cost of 18.
Example 3:
Input: baseCosts = [3,10], toppingCosts = [2,5], target = 9 Output: 8 Explanation: It is possible to make desserts with cost 8 and 10. Return 8 as it is the lower cost.
Constraints:
n == baseCosts.lengthm == toppingCosts.length1 <= n, m <= 101 <= baseCosts[i], toppingCosts[i] <= 1041 <= target <= 104Problem Overview: You’re given several base dessert costs and a list of topping costs. You must choose exactly one base and optionally add each topping 0, 1, or 2 times. The goal is to get a total cost as close as possible to a target value. If two totals are equally close, choose the smaller cost.
Approach 1: Brute Force with Recursion / Backtracking (Time: O(m * 3^n), Space: O(n))
This approach explores every possible topping combination. For each base cost, recursively decide whether to use a topping 0, 1, or 2 times. That creates a branching factor of 3 per topping, so with n toppings there are 3^n combinations. During recursion, compute the running total and track the value closest to the target. Backtracking works well because the topping count is small, and pruning can stop exploration when the cost already exceeds a clearly worse candidate.
The key idea is simple: iterate through each base cost, run a DFS that tries all topping counts, and update the best answer whenever the difference from the target improves. This method is straightforward and demonstrates how to systematically enumerate combinations using backtracking. Despite the exponential complexity, the constraints keep it practical.
Approach 2: Dynamic Programming (Time: O(n * target + m * target), Space: O(target))
The dynamic programming approach treats the toppings like a bounded knapsack problem. Each topping can be chosen twice, so you effectively process each topping two times in a DP array where dp[cost] indicates whether that cost is achievable using toppings. This builds all reachable topping totals up to the target.
Once possible topping sums are known, combine them with each base cost. For every base, check which topping total produces a dessert cost closest to the target. Since the DP array stores reachable sums efficiently, you avoid enumerating all 3^n combinations explicitly.
This technique relies on standard dynamic programming patterns used in subset-sum problems. The topping list behaves like a small array of weighted items with limited repetition. The result is a more scalable approach that runs in pseudo-polynomial time relative to the target value.
Recommended for interviews: Start with the recursive/backtracking solution to show you understand the combinational search space. Then discuss the dynamic programming optimization that treats toppings like a bounded knapsack. Interviewers typically expect the backtracking idea first, but the DP approach demonstrates stronger algorithmic thinking and better scalability.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion / Backtracking | O(m * 3^n) | O(n) | When topping count is small and you want the simplest implementation |
| Dynamic Programming (Bounded Knapsack) | O(n * target + m * target) | O(target) | Preferred when optimizing search by precomputing reachable topping costs |