Closest Dessert Cost - Solution & Explanation

Problem 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.