Closest Dessert Cost: Backtracking with Pruning

You are making ice cream. You have an array baseCosts where each entry is the cost of a different base flavor, an array toppingCosts where each entry is the cost of a topping type, and a target price you want to hit. You must pick exactly one base. For each topping, you can add it 0, 1, or 2 times. Return the cost closest to target. If two costs are equally close, return the lower one.

This is LeetCode 1774: Closest Dessert Cost, and it is an excellent problem for practicing backtracking with pruning. The decision tree is small enough to visualize completely, but large enough that naive brute force without pruning wastes significant work.

Why this problem matters

Closest Dessert Cost teaches you to think about backtracking not as "find all valid answers" but as "search for the best answer while cutting dead branches." Unlike Combination Sum, where you collect every combination that hits the target exactly, here you are optimizing: you want the single closest cost. That means you need to track a running best and use it to prune branches that cannot improve on what you have already found.

This is also a great introduction to the "3-way branching" pattern. Each topping gives you three choices (0, 1, or 2 copies), which creates a ternary decision tree. The total number of leaves is 3^m per base (where m is the number of toppings), so pruning matters. Without it, you explore every leaf. With it, you can skip entire subtrees once the current cost overshoots the target by more than the current best difference.

The key insight

For each base cost, you build a decision tree where each level corresponds to one topping. At each level, you branch three ways: add the topping 0 times, 1 time, or 2 times. The running cost grows as you descend. You track the globally closest cost seen so far. When the current cost already exceeds the target by more than the best difference you have recorded, you can stop exploring deeper, because adding more toppings only increases the cost further.

The tie-breaking rule ("return the lower cost") is handled naturally: when you find a cost whose absolute difference from the target equals the current best difference, you update only if the new cost is lower.

The solution

def closestCost(baseCosts, toppingCosts, target):
    best = float('inf')

    def dfs(index, cost):
        nonlocal best
        if abs(cost - target) < abs(best - target):
            best = cost
        elif abs(cost - target) == abs(best - target):
            best = min(best, cost)

        if index == len(toppingCosts):
            return
        if cost > target and cost - target >= abs(best - target):
            return

        for times in range(3):
            dfs(index + 1, cost + toppingCosts[index] * times)

    for base in baseCosts:
        dfs(0, base)

    return best

Let's walk through this.

The outer loop tries every base cost. For each one, it launches a DFS that explores the topping decision tree.

Inside dfs, the first thing we do is check whether the current cost is closer to the target than our best so far. If the difference is strictly smaller, we update. If the difference is tied, we take the lower cost (the tie-breaking rule).

The base case is reaching the end of the toppings array. At that point there are no more decisions to make, so we return.

The pruning check comes next: if the current cost already exceeds the target and the overshoot is at least as large as the best difference we have seen, there is no point adding more toppings. Every topping has a non-negative cost, so the total can only stay the same or increase. We cut the branch.

The three-way loop tries adding the current topping 0, 1, or 2 times, then recurses to the next topping index.

Visual walkthrough

Let's trace through the algorithm with baseCosts = [1, 7], toppingCosts = [3, 4], and target = 10. Watch how the search finds the exact match quickly and then prunes the remaining branches.

Notice how starting from base 7, the algorithm finds cost = 10 (an exact match) on the very first topping decision. After that, every branch that overshoots the target gets pruned because no overshoot can beat a difference of 0. The base-1 subtree still runs, but none of its paths produce a closer cost, so the answer stays at 10.

Complexity analysis

Time: For each of the n base costs, we explore a ternary tree of depth m (one level per topping). In the worst case, each node branches 3 ways, giving 3^m leaves per base. Pruning reduces this significantly in practice, but the worst case is O(n * 3^m).

Space: The recursion stack goes m levels deep (one per topping). We use O(1) extra space beyond the stack, so the total space is O(m).

The constraints for this problem are small (n and m up to 10), so even the unpruned brute force is fast enough. But the pruning technique generalizes to larger problems where it becomes essential.

The building blocks

1. Three-way branching (ternary decision tree)

At each topping, you have exactly three choices: use it 0, 1, or 2 times. This is a constrained version of the general backtracking template:

for times in range(3):
    dfs(index + 1, cost + toppingCosts[index] * times)

This pattern shows up whenever each item has a fixed, small number of uses. If the problem said "up to k times," you would loop range(k + 1) instead. The same structure applies to problems like Target Sum (two choices per element: add or subtract) or Combination Sum II (zero or one use per element).

2. Best-so-far pruning

Unlike problems where you collect all valid answers, here you track the single best answer and use it to cut branches:

if cost > target and cost - target >= abs(best - target):
    return

This is a general optimization technique. Any time you are searching for an optimal value (minimum, closest, maximum), you can prune branches that provably cannot beat the current best. The tighter your bound, the more you prune.

Edge cases

Before submitting, check these:

• Target equals a base cost: baseCosts = [10], toppingCosts = [1], target = 10. The answer is 10 with zero toppings added. Make sure you do not force at least one topping.
• All costs overshoot: baseCosts = [10], toppingCosts = [5], target = 3. The closest is 10 (just the base, no toppings). You cannot remove cost, only add.
• Tie-breaking: baseCosts = [2, 3], toppingCosts = [], target = 2. Both 2 and 3 are valid base-only costs, but 2 is closer. If target = 2 and the costs are equally close (like 1 and 3, both diff = 1), return the lower one: 1.
• Single base, single topping: baseCosts = [5], toppingCosts = [3], target = 9. Costs are 5, 8, 11. The closest is 8 (diff = 1) since 11 has diff = 2.
• All toppings used twice hits exact target: Make sure your code handles the exact match and stops looking further.

From understanding to recall

You understand the ternary decision tree. You see how "best-so-far pruning" cuts branches once you have a good answer. But can you write the DFS with the pruning condition and the tie-breaking logic from scratch in under two minutes?

That is what interviews demand. Under pressure, small details trip people up: forgetting the tie-breaking rule, writing the pruning condition incorrectly, or looping range(2) instead of range(3). These are not conceptual gaps. They are recall problems.

Spaced repetition fixes recall. You practice writing the three-way branching loop and the pruning check from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "closest cost" and the DFS template flows out without hesitation.

Related posts

• Combination Sum - Another backtracking problem with a target sum, but collecting all valid combinations instead of finding the closest one.
• Subsets - The foundational backtracking pattern for exploring all subsets. Closest Dessert Cost is a constrained, optimized version of subset enumeration.
• Target Sum - Two-way branching (add or subtract) to hit a target. Similar "track best" structure, often solved with DP.

CodeBricks breaks Closest Dessert Cost into its reusable building blocks: three-way branching and best-so-far pruning. You drill each one independently with spaced repetition until writing the backtracking loop and the pruning check is automatic. When a "find the closest" problem shows up in your interview, you do not think about it. You just write it.