Closest dessert cost

Array Dynamic Programming Backtracking

48.4% acceptance

Feb 25, 2026

733

You would like to make dessert and are preparing to buy the ingredients. 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. Return the closest possible cost of the dessert to target. If there are multiple, return the lower one.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn closest_cost(base_costs: Vec<i32>, topping_costs: Vec<i32>, target: i32) -> i32 {
    let mut best = i32::MAX;
    let _m = topping_costs.len();

    fn dfs(idx: usize, current: i32, toppings: &[i32], target: i32, best: &mut i32) {
      let diff_best = ((*best) - target).abs();
      let diff_cur = (current - target).abs();
      if diff_cur < diff_best || (diff_cur == diff_best && current < *best) {
        *best = current;
      }
      if idx == toppings.len() || current >= target { return; }
      for count in 0..=2 {
        dfs(idx + 1, current + count * toppings[idx], toppings, target, best);
      }
    }

    for &base in &base_costs {
      dfs(0, base, &topping_costs, target, &mut best);
    }
    best
  }
}