Skip to main content
Talentd

Closest Dessert Cost - Solution & Explanation

MediumArrayDynamic ProgrammingBacktracking17 min readAsked at: Google
Practice this problem

Problem Statement

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:

  • There must be exactly one ice cream base.
  • You can add one or more types of topping or have no toppings at all.
  • There are at most two of each type of topping.

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.length
  • m == toppingCosts.length
  • 1 <= n, m <= 10
  • 1 <= baseCosts[i], toppingCosts[i] <= 104
  • 1 <= target <= 104

Approach Overview

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.

Approach 1: Brute Force with Recursion

The brute force approach involves examining all possible combinations of ice cream base and toppings costs. We select one of the base costs, and then recursively generate all valid combinations of toppings, making use of each topping either 0, 1, or 2 times. Track the combination offering the cost closest to the target. This approach, though straightforward, might be inefficient for larger inputs due to the exponential growth of combinations.

This solution uses a depth-first search to explore all combinations. It iterates through each base cost, initiating a recursive search on toppings. For each topping, three choices are considered: using it 0, 1, or 2 times. The closest possible cost is updated if a better (i.e., closer) combination is found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(3^m * n), where m is the number of toppings, and n is the number of bases.
Space complexity: O(m) for the recursion stack.

Try this approach in the editor β†’

Approach 2: Dynamic Programming Approach

In this approach, dynamic programming is used to evaluate all prospective combinations of bases and toppings. By employing a boolean DP array, for example, dp[i], represent a feasible topping cost total i. The procedure begins by setting all base costs in the DP list and sequentially assesses each topping, supporting up to two per type. The optimal cost is returned when the closest sum to the target is achieved.

The Python version employs dynamic programming. The boolean DP array represents achievable costs using a set of bases and as many toppings as necessary. The array is initialized using base costs and subsequently expanded with possible topping additions.

Code

PythonJavaC++

Python

Java

C++

Complexity

Time Complexity: O(n + m * T), where n is the number of baseCosts and m is the number of toppingCosts; T is the total topping costs.
Space Complexity: O(T) for storing feasible costs.

Try this approach in the editor β†’

Approach 3: Default Approach

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
Brute Force with Recursion

Time complexity: O(3^m * n), where m is the number of toppings, and n is the number of bases.
Space complexity: O(m) for the recursion stack.

Dynamic Programming Approach

Time Complexity: O(n + m * T), where n is the number of baseCosts and m is the number of toppingCosts; T is the total topping costs.
Space Complexity: O(T) for storing feasible costs.

Default Approachβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Recursion / BacktrackingO(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

Video Solution

LeetCode 1774. Closest Dessert Cost | Weekly Contest 230| Medium | Algorithm Explained | C++ β€’ Cherry Coding [IIT-G] β€’ 2,064 views views

Watch 9 more video solutions β†’

Frequently Asked Questions

Is Closest Dessert Cost easy or hard?
Closest Dessert Cost is classified as a Medium problem on LeetCode. The brute-force idea is straightforward, but recognizing pruning strategies or converting the problem into a bounded knapsack dynamic programming solution requires stronger algorithmic insight.
What is the best approach for Closest Dessert Cost?
The most practical approach is backtracking that tries each topping 0, 1, or 2 times for every base cost. This explores all combinations with complexity O(m * 3^n) and works well because the number of toppings is small. A dynamic programming variation using a bounded knapsack can further optimize the search by precomputing reachable topping sums.
Is Closest Dessert Cost asked at Google/Amazon/Meta?
Closest Dessert Cost represents a typical combinational search and bounded knapsack style interview problem. Variants of this pattern appear in interviews at companies like Amazon and Google where candidates must explore combinations efficiently or apply dynamic programming.
What data structure is used in Closest Dessert Cost?
The solution mainly uses arrays and recursion. Backtracking relies on recursive DFS over the topping array, while the optimized method uses a DP array or set to store reachable topping costs. These structures help efficiently evaluate combinations.
What is the time complexity of Closest Dessert Cost?
The recursive backtracking solution runs in O(m * 3^n) time where m is the number of base costs and n is the number of toppings. Each topping has three choices (0, 1, or 2). A dynamic programming solution reduces repeated work and runs in roughly O(n * target + m * target) time with O(target) space.
Closest Dessert Cost Python or Java solution approach?
In Python or Java, implement a DFS that iterates through toppings and tries adding 0, 1, or 2 units while tracking the closest value to the target. For the dynamic programming approach, maintain a boolean array representing reachable topping sums and combine it with each base cost.
How to solve Closest Dessert Cost in O(n) or optimized time?
An optimized method uses dynamic programming similar to the subset sum problem. Treat each topping as available twice and build a boolean DP array of reachable topping costs up to the target. Then combine each base cost with those topping sums to find the value closest to the target.

Ready to solve this problem?

Practice Closest Dessert Cost with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays