Closest Dessert Cost solution and explanation
Google
9 more videos on this problem
LeetCode 1774. Closest Dessert Cost | Weekly Contest 230| Medium | Algorithm Explained | C++Cherry Coding [IIT-G] · 8:14 · 2K views
Leetcode Weekly Contest 230 | Count Items Matching a Rule | Closest Dessert Costcode Explainer · 15:46 · 1K views
LeetCode 1774. Closest Dessert CostHappy Coding · 13:56 · 1K views
LeetCode 1774. Closest Dessert Cost | Visualization | PythonAH Tech · 6:42 · 566 views
1774. Closest Dessert Cost (Leetcode Medium)Programming Live with Larry · 11:01 · 542 views
【每日一题】LeetCode 1774. Closest Dessert CostHuifeng Guan · 11:49 · 398 views
Leetcode 1774. Closest Dessert CostElite Code · 25:16 · 373 views
LeetCode #1774 - Closest Dessert Cost: BacktrackingGDSC FIU · 13:28 · 233 views
Leetcode 1774. Closest Dessert Cost Explanation & Code DFSBrittany · 11:52 · 206 views
LeetCode 1774. Closest Dessert Cost宰相小甘罗 · 4:28 · 181 views
The problem
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 lengthn, where eachbaseCosts[i]represents the price of theithice cream base flavor.toppingCosts, an integer array of lengthm, where eachtoppingCosts[i]is the price of one of theithtopping.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 <= 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.
def dfs(toppingCosts, index, currentCost, target, closest):
if index == len(toppingCosts):
if abs(currentCost - target) < abs(closest.value - target) or \
(abs(currentCost - target) == abs(closest.value - target) and currentCost < closest.value):
closest.value = currentCost
return
dfs(toppingCosts, index + 1, currentCost, target, closest)
dfs(toppingCosts, index + 1, currentCost + toppingCosts[index], target, closest)
dfs(toppingCosts, index + 1, currentCost + 2 * toppingCosts[index], target, closest)
class Closest:
def __init__(self):
self.value = float('inf')
def closestCost(baseCosts, toppingCosts, target):
closest = Closest()
for base in baseCosts:
dfs(toppingCosts, 0, base, target, closest)
return closest.value
baseCosts = [1, 7]
toppingCosts = [3, 4]
target = 10
print(closestCost(baseCosts, toppingCosts, target))import java.util.*;
public class ClosestDessertCost {
private static void dfs(int[] toppingCosts, int index, int currentCost, int target, int[] closest) {
if (index == toppingCosts.length) {
if (Math.abs(currentCost - target) < Math.abs(closest[0] - target) ||
(Math.abs(currentCost - target) == Math.abs(closest[0] - target) && currentCost < closest[0])) {
closest[0] = currentCost;
}
return;
}
dfs(toppingCosts, index + 1, currentCost, target, closest);
dfs(toppingCosts, index + 1, currentCost + toppingCosts[index], target, closest);
dfs(toppingCosts, index + 1, currentCost + 2 * toppingCosts[index], target, closest);
}
public static int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
int[] closest = {Integer.MAX_VALUE};
for (int base : baseCosts) {
dfs(toppingCosts, 0, base, target, closest);
}
return closest[0];
}
public static void main(String[] args) {
int[] baseCosts = {1, 7};
int[] toppingCosts = {3, 4};
int target = 10;
System.out.println(closestCost(baseCosts, toppingCosts, target));
}
}#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;
void dfs(vector<int>& toppingCosts, int index, int currentCost, int target, int& closest) {
if (index == toppingCosts.size()) {
if (abs(currentCost - target) < abs(closest - target) ||
(abs(currentCost - target) == abs(closest - target) && currentCost < closest)) {
closest = currentCost;
}
return;
}
dfs(toppingCosts, index + 1, currentCost, target, closest);
dfs(toppingCosts, index + 1, currentCost + toppingCosts[index], target, closest);
dfs(toppingCosts, index + 1, currentCost + 2 * toppingCosts[index], target, closest);
}
int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
int closest = INT_MAX;
for (int base : baseCosts) {
dfs(toppingCosts, 0, base, target, closest);
}
return closest;
}
int main() {
vector<int> baseCosts = {1, 7};
vector<int> toppingCosts = {3, 4};
int target = 10;
cout << closestCost(baseCosts, toppingCosts, target) << endl;
return 0;
}function dfs(toppingCosts, index, currentCost, target, closest) {
if (index === toppingCosts.length) {
if (Math.abs(currentCost - target) < Math.abs(closest.value - target) ||
(Math.abs(currentCost - target) === Math.abs(closest.value - target) && currentCost < closest.value)) {
closest.value = currentCost;
}
return;
}
dfs(toppingCosts, index + 1, currentCost, target, closest);
dfs(toppingCosts, index + 1, currentCost + toppingCosts[index], target, closest);
dfs(toppingCosts, index + 1, currentCost + 2 * toppingCosts[index], target, closest);
}
function closestCost(baseCosts, toppingCosts, target) {
let closest = { value: Infinity };
for (let base of baseCosts) {
dfs(toppingCosts, 0, base, target, closest);
}
return closest.value;
}
let baseCosts = [1, 7];
let toppingCosts = [3, 4];
let target = 10;
console.log(closestCost(baseCosts, toppingCosts, target));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
void dfs(int *toppingCosts, int m, int index, int currentCost, int target, int *closest) {
if (index == m) {
if (abs(currentCost - target) < abs(*closest - target) ||
(abs(currentCost - target) == abs(*closest - target) && currentCost < *closest)) {
*closest = currentCost;
}
return;
}
dfs(toppingCosts, m, index + 1, currentCost, target, closest); // Choose 0 of current topping
dfs(toppingCosts, m, index + 1, currentCost + toppingCosts[index], target, closest); // Choose 1 of current topping
dfs(toppingCosts, m, index + 1, currentCost + 2 * toppingCosts[index], target, closest); // Choose 2 of current topping
}
int closestCost(int *baseCosts, int n, int *toppingCosts, int m, int target) {
int closest = INT_MAX;
for (int i = 0; i < n; i++) {
dfs(toppingCosts, m, 0, baseCosts[i], target, &closest);
}
return closest;
}
int main() {
int baseCosts[] = {1, 7};
int toppingCosts[] = {3, 4};
int target = 10;
printf("%d\n", closestCost(baseCosts, 2, toppingCosts, 2, target));
return 0;
}using System;
class ClosestDessertCost {
private static void Dfs(int[] toppingCosts, int index, int currentCost, int target, ref int closest) {
if (index == toppingCosts.Length) {
if (Math.Abs(currentCost - target) < Math.Abs(closest - target) ||
(Math.Abs(currentCost - target) == Math.Abs(closest - target) && currentCost < closest)) {
closest = currentCost;
}
return;
}
Dfs(toppingCosts, index + 1, currentCost, target, ref closest);
Dfs(toppingCosts, index + 1, currentCost + toppingCosts[index], target, ref closest);
Dfs(toppingCosts, index + 1, currentCost + 2 * toppingCosts[index], target, ref closest);
}
public static int ClosestCost(int[] baseCosts, int[] toppingCosts, int target) {
int closest = int.MaxValue;
foreach (int baseCost in baseCosts) {
Dfs(toppingCosts, 0, baseCost, target, ref closest);
}
return closest;
}
public static void Main() {
int[] baseCosts = {1, 7};
int[] toppingCosts = {3, 4};
int target = 10;
Console.WriteLine(ClosestCost(baseCosts, toppingCosts, target));
}
}In Python, this solution uses a recursive helper function dfs to explore each topping combination similarly to other implementations. A class Closest tracks the best cost so far to enable modification across recursive calls.
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.
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.
def closestCost(baseCosts, toppingCosts, target):
maxCost = 2 * sum(toppingCosts) + max(baseCosts)
dp = [False] * (maxCost + 1)
for b in baseCosts:
dp[b] = True
for topping in toppingCosts:
for count in range(2):
for cost in range(maxCost, topping - 1, -1):
if dp[cost - topping]:
dp[cost] = True
diff = float('inf')
closest = None
for cost in range(maxCost + 1):
if dp[cost]:
if abs(cost - target) < diff:
diff = abs(cost - target)
closest = cost
return closest
baseCosts = [1, 7]
toppingCosts = [3, 4]
target = 10
print(closestCost(baseCosts, toppingCosts, target))import java.util.Arrays;
public class ClosestDessertCost {
public static int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
int maxCost = 2 * Arrays.stream(toppingCosts).sum() + Arrays.stream(baseCosts).max().getAsInt();
boolean[] dp = new boolean[maxCost + 1];
for (int b : baseCosts) {
dp[b] = true;
}
for (int topping : toppingCosts) {
for (int i = 0; i < 2; i++) {
for (int cost = maxCost; cost >= topping; cost--) {
if (dp[cost - topping]) {
dp[cost] = true;
}
}
}
}
int closest = Integer.MAX_VALUE;
int diff = Integer.MAX_VALUE;
for (int cost = 0; cost <= maxCost; cost++) {
if (dp[cost]) {
if (Math.abs(cost - target) < diff || (Math.abs(cost - target) == diff && cost < closest)) {
diff = Math.abs(cost - target);
closest = cost;
}
}
}
return closest;
}
public static void main(String[] args) {
int[] baseCosts = {1, 7};
int[] toppingCosts = {3, 4};
int target = 10;
System.out.println(closestCost(baseCosts, toppingCosts, target));
}
}#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
int closestCost(std::vector<int>& baseCosts, std::vector<int>& toppingCosts, int target) {
int maxCost = 2 * std::accumulate(toppingCosts.begin(), toppingCosts.end(), 0) + *std::max_element(baseCosts.begin(), baseCosts.end());
std::vector<bool> dp(maxCost + 1, false);
for (int b : baseCosts) {
dp[b] = true;
}
for (int topping : toppingCosts) {
for (int count = 0; count < 2; ++count) {
for (int cost = maxCost; cost >= topping; --cost) {
if (dp[cost - topping]) {
dp[cost] = true;
}
}
}
}
int closest = INT_MAX;
int diff = INT_MAX;
for (int cost = 0; cost <= maxCost; ++cost) {
if (dp[cost]) {
if (abs(cost - target) < diff || (abs(cost - target) == diff && cost < closest)) {
diff = abs(cost - target);
closest = cost;
}
}
}
return closest;
}
int main() {
std::vector<int> baseCosts = {1, 7};
std::vector<int> toppingCosts = {3, 4};
int target = 10;
std::cout << closestCost(baseCosts, toppingCosts, target) << std::endl;
return 0;
}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.
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.
Approach 3: Default Approach
func closestCost(baseCosts []int, toppingCosts []int, target int) int {
arr := []int{}
var dfs func(int, int)
dfs = func(i, t int) {
if i >= len(toppingCosts) {
arr = append(arr, t)
return
}
dfs(i+1, t)
dfs(i+1, t+toppingCosts[i])
}
dfs(0, 0)
sort.Ints(arr)
const inf = 1 << 30
ans, d := inf, inf
// 选择一种冰激淋基料
for _, x := range baseCosts {
// 枚举子集和
for _, y := range arr {
// 二分查找
i := sort.SearchInts(arr, target-x-y)
for j := i - 1; j < i+1; j++ {
if j >= 0 && j < len(arr) {
t := abs(x + y + arr[j] - target)
if d > t || (d == t && ans > x+y+arr[j]) {
d = t
ans = x + y + arr[j]
}
}
}
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force with Recursion | Time complexity: O(3^m * n), where m is the number of toppings, and n is the number of bases. |
| 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. |
| Default Approach | – |
Complexity analysis
| 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 |
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.