Closest Dessert Cost - Practice Coding Problems

Closest Dessert Cost - 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 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.

Input & Output

Example 1 — Basic Case

$ Input: baseCosts = [1,7], toppingCosts = [3,4], target = 10

› Output: 10

💡 Note: Consider base cost 7 with 1 topping of cost 3: 7 + 3 = 10, which exactly equals target 10

Example 2 — Multiple Closest

$ Input: baseCosts = [2,3], toppingCosts = [4,5,100], target = 18

› Output: 17

💡 Note: Base 3 + 2×4 + 2×5 = 3 + 8 + 10 = 21 (distance 3), Base 2 + 2×4 + 1×5 = 2 + 8 + 5 = 15 (distance 3), and Base 3 + 2×4 + 1×5 = 17 (distance 1). The closest is 17.

Example 3 — Lower Cost Tie

$ Input: baseCosts = [3,10], toppingCosts = [2,5], target = 9

› Output: 8

💡 Note: Base 3 + 1×5 = 8 (distance 1), Base 10 + 0 toppings = 10 (distance 1). Both have same distance but 8 < 10, so return 8

Constraints

n == baseCosts.length
m == toppingCosts.length
1 ≤ n, m ≤ 10
1 ≤ baseCosts[i], toppingCosts[i] ≤ 10⁴
1 ≤ target ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Base costs [1,7], topping costs [3,4], target 10

Process

Try each base with all possible topping combinations (0-2 of each)

Output

Return cost closest to target (prefer lower if tie)

Key Takeaway

🎯 Key Insight: Use backtracking to explore all base + topping combinations, track closest to target

Asked in

a Amazon 15 G Google 8

The key insight is to use backtracking to explore all possible dessert combinations: exactly one base + 0-2 of each topping. Best approach is memoized backtracking to avoid recalculating topping combinations. Time: O(n × 3^m), Space: O(3^m)

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Backtracking	O(n × 3^m)	O(3^m + m)	Cache results of topping combinations to avoid redundant calculations
Brute Force with Backtracking	O(n × 3^m)	O(m)	Try every possible combination of base and toppings using recursive backtracking

Memoized Backtracking — Algorithm Steps

Step 1: Create a memo map to cache topping combination results
Step 2: For each base, use memoized backtracking on toppings
Step 3: Return cached result if combination already computed

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Toppings

Calculate all possible topping sums once

Cache Results

Store combinations in memo to avoid recalculation

Try All Bases

Combine each base with pre-computed topping sums

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_SUMS 10000

int memo[20][MAX_SUMS];
int memoSize[20];
int memoValid[20];

void getToppingSums(int* toppingCosts, int toppingSize, int index, int* sums, int* sumSize) {
    if (index >= toppingSize) {
        sums[0] = 0;
        *sumSize = 1;
        return;
    }
    
    if (memoValid[index]) {
        for (int i = 0; i < memoSize[index]; i++) {
            sums[i] = memo[index][i];
        }
        *sumSize = memoSize[index];
        return;
    }
    
    int nextSums[MAX_SUMS];
    int nextSize;
    getToppingSums(toppingCosts, toppingSize, index + 1, nextSums, &nextSize);
    
    int currentSize = 0;
    // Try 0, 1, or 2 of current topping
    for (int count = 0; count < 3; count++) {
        for (int i = 0; i < nextSize; i++) {
            sums[currentSize] = count * toppingCosts[index] + nextSums[i];
            memo[index][currentSize] = sums[currentSize];
            currentSize++;
        }
    }
    
    memoSize[index] = currentSize;
    memoValid[index] = 1;
    *sumSize = currentSize;
}

int solution(int* baseCosts, int baseSize, int* toppingCosts, int toppingSize, int target) {
    memset(memoValid, 0, sizeof(memoValid));
    
    int closestDistance = INT_MAX;
    int result = INT_MAX;
    
    // Get all possible topping combinations
    int toppingSums[MAX_SUMS];
    int toppingSumSize;
    getToppingSums(toppingCosts, toppingSize, 0, toppingSums, &toppingSumSize);
    
    // Try each base with each topping combination
    for (int i = 0; i < baseSize; i++) {
        for (int j = 0; j < toppingSumSize; j++) {
            int totalCost = baseCosts[i] + toppingSums[j];
            int distance = abs(totalCost - target);
            
            if (distance < closestDistance || (distance == closestDistance && totalCost < result)) {
                closestDistance = distance;
                result = totalCost;
            }
        }
    }
    
    return result;
}

int main() {
    char line[1000];
    
    // Parse baseCosts
    fgets(line, sizeof(line), stdin);
    int baseCosts[50], baseSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        baseCosts[baseSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    // Parse toppingCosts
    fgets(line, sizeof(line), stdin);
    int toppingCosts[50], toppingSize = 0;
    token = strtok(line, "[],\n");
    while (token != NULL) {
        toppingCosts[toppingSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    // Parse target
    int target;
    scanf("%d", &target);
    
    int res = solution(baseCosts, baseSize, toppingCosts, toppingSize, target);
    printf("%d\n", res);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 3^m)

Memoization helps but worst case is still 3^m topping combinations for n bases

✓ Linear Growth

Space Complexity

O(3^m + m)

Memo cache stores up to 3^m states plus recursion stack depth m

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler