Closest Dessert Cost

Med

#1624Time: O(n * 3^m), where `n` is the number of base flavors and `m` is the number of toppings. For each of the `n` base costs, we explore a ternary tree of depth `m`.Space: O(m), where `m` is the number of toppings. This is the maximum depth of the recursion stack.

Patterns

Dynamic Programming Backtracking

Data structures

Array

Prompt

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 i^th ice cream base flavor.
toppingCosts, an integer array of length m, where each toppingCosts[i] is the price of one of the i^th 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] <= 10⁴
1 <= target <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically explores all possible dessert combinations using a recursive depth-first search (DFS). For each of the n base flavors, we recursively try every possible topping combination. For each of the m toppings, there are three choices: take zero, one, or two. This creates a search space of 3^m topping combinations for each base.

Algorithm

Initialize a global variable result to hold the closest cost found so far. A good initial value is the cost of the first base flavor.
Iterate through each baseCost in the baseCosts array.
For each baseCost, call a recursive helper function, dfs(toppingCosts, index, currentCost).
The dfs function explores the choices for toppings starting from index.
In each call to dfs, first check if the currentCost is a better answer than the current result. A cost is "better" if it's closer to the target, or if it's equally close but lower in value.
The recursion has a base case: when index equals the number of toppings, we have considered all toppings and the recursion for that path stops.
As an optimization (pruning), if the currentCost already exceeds the target and is worse than the current best answer result, we can stop exploring that path, as adding more (positive cost) toppings will only make the cost higher and the result worse.
The recursive step involves making three calls for the topping at index:
1. dfs(toppingCosts, index + 1, currentCost): Skip the current topping.
2. dfs(toppingCosts, index + 1, currentCost + toppingCosts[index]): Add one of the current topping.
3. dfs(toppingCosts, index + 1, currentCost + 2 * toppingCosts[index]): Add two of the current topping.
After the initial loop over base costs completes, result will contain the final answer.

Walkthrough

We initialize a variable, result, to hold the closest cost found so far. A good initial value is the cost of the first base flavor. We then iterate through each baseCost in the baseCosts array. For each baseCost, we start a recursive function, dfs(toppingCosts, index, currentCost), which explores the choices for toppings starting from index. In each call to dfs, we first check if the currentCost is a better answer than our current result. A cost is "better" if it's closer to the target, or if it's equally close but lower in value. The recursion has a base case for when index equals the number of toppings. As an optimization (pruning), if the currentCost already exceeds the target and is worse than the current best answer result, we can stop exploring that path. The recursive step involves making three calls for the topping at index: one for skipping the topping, one for adding it once, and one for adding it twice. After the initial loop over base costs completes, result will contain the final answer.

1class Solution {2    int result;3    int target;4 5    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {6        this.result = baseCosts[0];7        this.target = target;8        for (int base : baseCosts) {9            dfs(toppingCosts, 0, base);10        }11        return result;12    }13 14    private void dfs(int[] toppingCosts, int index, int currentCost) {15        int currentDiff = Math.abs(currentCost - target);16        int resultDiff = Math.abs(result - target);17 18        if (currentDiff < resultDiff || (currentDiff == resultDiff && currentCost < result)) {19            result = currentCost;20        }21 22        // Base case and pruning23        if (index == toppingCosts.length || currentCost > target && currentCost > result) {24            return;25        }26 27        // Recursive calls for the next topping28        // Choice 1: 0 of current topping29        dfs(toppingCosts, index + 1, currentCost);30        // Choice 2: 1 of current topping31        dfs(toppingCosts, index + 1, currentCost + toppingCosts[index]);32        // Choice 3: 2 of current topping33        dfs(toppingCosts, index + 1, currentCost + 2 * toppingCosts[index]);34    }35}

Complexity

Time

O(n * 3^m), where `n` is the number of base flavors and `m` is the number of toppings. For each of the `n` base costs, we explore a ternary tree of depth `m`.

Space

O(m), where `m` is the number of toppings. This is the maximum depth of the recursion stack.

Trade-offs

Pros

Conceptually straightforward and follows the problem statement directly.
Low space complexity.

Cons

Exponential time complexity, which is only feasible because the constraints on m are very small.
Can be slower than dynamic programming for certain inputs due to recursion overhead.

This approach uses dynamic programming to determine all possible costs that can be achieved. It's a variation of the knapsack problem. We build up a set of achievable costs by iteratively adding the toppings. This avoids recursion overhead and can be more efficient for the given constraints.

Algorithm

Define a maxCost limit (e.g., 30000), which is a safe upper bound for the answer.
Create a boolean array dp of size maxCost + 1 to store achievable costs.
Initialize the dp array by setting dp[base] = true for each base in baseCosts.
For each tCost in toppingCosts:
- To simulate adding the topping at most twice, run the following loop twice:
- For c from maxCost down to tCost: dp[c] = dp[c] || dp[c - tCost]. The backward iteration ensures each unit of the topping is considered at most once per pass.
After populating the dp array, iterate from c = 1 to maxCost.
Initialize result and minDiff to track the best answer.
If dp[c] is true, calculate its difference from target and update result and minDiff if it's a better match (smaller difference, or same difference with a lower cost).
Return result.

Walkthrough

First, we determine the set of all possible total costs using a boolean array, possibleCosts, where possibleCosts[c] is true if a dessert of cost c can be made. We need to establish a maximum possible cost to size the array; a value like 30000 is a safe upper bound given the problem constraints. We initialize the possibleCosts array by marking the costs of all base flavors as true. Then, for each toppingCost, we update the possibleCosts array. To model taking a topping 0, 1, or 2 times, we can treat it as having two identical items of that topping. We iterate through the possibleCosts array backwards for each of these two items, which correctly updates the achievable costs. After processing all toppings, the possibleCosts array is fully populated. Finally, we iterate through this array to find the cost c that is closest to the target, handling ties by choosing the lower cost.

1class Solution {2    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {3        int maxCost = 30000; // A safe upper bound for cost4        boolean[] possible = new boolean[maxCost + 1];5        6        for (int base : baseCosts) {7            if (base <= maxCost) {8                possible[base] = true;9            }10        }11        12        for (int topping : toppingCosts) {13            // We can add each topping up to two times.14            // We run the loop twice to simulate adding one or two toppings.15            // The backward iteration prevents using the same topping unit multiple times in one go.16            for (int i = 0; i < 2; i++) {17                for (int cost = maxCost; cost >= topping; cost--) {18                    if (possible[cost - topping]) {19                        possible[cost] = true;20                    }21                }22            }23        }24        25        int result = Integer.MAX_VALUE;26        int minDiff = Integer.MAX_VALUE;27        28        for (int cost = 1; cost <= maxCost; cost++) {29            if (possible[cost]) {30                int diff = Math.abs(cost - target);31                if (diff < minDiff) {32                    minDiff = diff;33                    result = cost;34                } else if (diff == minDiff) {35                    result = Math.min(result, cost);36                }37            }38        }39        return result;40    }41}

Complexity

Time

O(n + m*C), where `n` is the number of bases, `m` is the number of toppings, and `C` is the maximum cost considered. Initializing takes `O(n)`, the DP update takes `O(m*C)`, and the final search takes `O(C)`.

Space

O(C), where `C` is the maximum cost considered. We need a boolean array of size `C` to store the possible costs.

Trade-offs

Pros

Generally faster than backtracking for the given constraints.
Avoids recursion overhead and potential stack overflow issues with deeper recursion.

Cons

Higher space complexity than the backtracking approach.
Complexity depends on the magnitude of costs (pseudo-polynomial), which could be a drawback if costs were very large.

Solutions

Solution

1class Solution {2private3  List<Integer> arr = new ArrayList<>();4private5  int[] ts;6private7  int inf = 1 << 30;8public9  int closestCost(int[] baseCosts, int[] toppingCosts, int target) {10    ts = toppingCosts;11    dfs(0, 0);12    Collections.sort(arr);13    int d = inf, ans = inf;

1const closestCost = function ( baseCosts , toppingCosts , target ) { let closestDessertCost = - Infinity ; function dfs ( dessertCost , j ) { const tarCurrDiff = Math . abs ( target - dessertCost ); const tarCloseDiff = Math . abs ( target - closestDessertCost ); if ( tarCurrDiff < tarCloseDiff ) { closestDessertCost = dessertCost ; } else if ( tarCurrDiff === tarCloseDiff && dessertCost < closestDessertCost ) { closestDessertCost = dessertCost ; } if ( dessertCost > target ) return ; if ( j === toppingCosts . length ) return ; for ( let count = 0 ; count <= 2 ; count ++ ) { dfs ( dessertCost + count * toppingCosts [ j ], j + 1 ); } } for ( let i = 0 ; i < baseCosts . length ; i ++ ) { dfs ( baseCosts [ i ], 0 ); } return closestDessertCost ; };

1class Solution {2public:3  const int inf = INT_MAX;4  int closestCost(vector<int> &baseCosts, vector<int> &toppingCosts,5                  int target) {6    vector<int> arr;7    function<void(int, int)> dfs = [&](int i, int t) {8      if (i >= toppingCosts.size()) {9        arr.push_back(t);10        return;11      }12      dfs(i + 1, t);13      dfs(i + 1, t + toppingCosts[i]);14    };15    dfs(0, 0);16    sort(arr.begin(), arr.end());17    int d = inf, ans = inf;

1class Solution:2    # 选择一种冰激淋基料 for x in baseCosts : # 枚举子集和 for y in arr : # 二分查找 i = bisect_left ( arr , target - x - y ) for j in ( i , i - 1 ): if 0 <= j < len ( arr ): t = abs ( x + y + arr [ j ] - target ) if d > t or ( d == t and ans > x + y + arr [ j ]): d = t ans = x + y + arr [ j ] return ans3    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int: def dfs(i, t): if i >= len(toppingCosts): arr . append(t) return dfs(i + 1, t) dfs(i + 1, t + toppingCosts[i]) arr = [] dfs(0, 0) arr . sort() d = ans = inf

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem