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 totarget. If there are multiple, return thelower one.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7
8

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

1
2
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^4
  • 1 <= target <= 10^4

Solution

Method 1 – Backtracking (DFS)

Intuition

We want to try all possible combinations of base and toppings (each topping can be used 0, 1, or 2 times) and find the cost closest to the target. Backtracking (DFS) is suitable since the number of toppings is small.

Approach

  1. For each base cost, use DFS to try all topping combinations (0, 1, or 2 of each topping).
  2. For each combination, calculate the total cost and update the answer if it’s closer to the target (or smaller if equally close).
  3. Return the closest cost found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int ans;
    void dfs(vector<int>& t, int i, int cost, int target) {
        if (abs(cost - target) < abs(ans - target) || (abs(cost - target) == abs(ans - target) && cost < ans))
            ans = cost;
        if (i == t.size() || cost > target + abs(ans - target)) return;
        dfs(t, i + 1, cost, target);
        dfs(t, i + 1, cost + t[i], target);
        dfs(t, i + 1, cost + 2 * t[i], target);
    }
    int closestCost(vector<int>& base, vector<int>& t, int target) {
        ans = base[0];
        for (int b : base) dfs(t, 0, b, target);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func closestCost(baseCosts, toppingCosts []int, target int) int {
    ans := baseCosts[0]
    var dfs func(i, cost int)
    dfs = func(i, cost int) {
        if abs(cost-target) < abs(ans-target) || (abs(cost-target) == abs(ans-target) && cost < ans) {
            ans = cost
        }
        if i == len(toppingCosts) || cost > target+abs(ans-target) {
            return
        }
        dfs(i+1, cost)
        dfs(i+1, cost+toppingCosts[i])
        dfs(i+1, cost+2*toppingCosts[i])
    }
    for _, b := range baseCosts {
        dfs(0, b)
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    int ans;
    public int closestCost(int[] base, int[] t, int target) {
        ans = base[0];
        for (int b : base) dfs(t, 0, b, target);
        return ans;
    }
    void dfs(int[] t, int i, int cost, int target) {
        if (Math.abs(cost - target) < Math.abs(ans - target) || (Math.abs(cost - target) == Math.abs(ans - target) && cost < ans))
            ans = cost;
        if (i == t.length || cost > target + Math.abs(ans - target)) return;
        dfs(t, i + 1, cost, target);
        dfs(t, i + 1, cost + t[i], target);
        dfs(t, i + 1, cost + 2 * t[i], target);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    var ans = 0
    fun closestCost(base: IntArray, t: IntArray, target: Int): Int {
        ans = base[0]
        for (b in base) dfs(t, 0, b, target)
        return ans
    }
    fun dfs(t: IntArray, i: Int, cost: Int, target: Int) {
        if (kotlin.math.abs(cost - target) < kotlin.math.abs(ans - target) || (kotlin.math.abs(cost - target) == kotlin.math.abs(ans - target) && cost < ans))
            ans = cost
        if (i == t.size || cost > target + kotlin.math.abs(ans - target)) return
        dfs(t, i + 1, cost, target)
        dfs(t, i + 1, cost + t[i], target)
        dfs(t, i + 1, cost + 2 * t[i], target)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def closestCost(self, baseCosts: list[int], toppingCosts: list[int], target: int) -> int:
        ans = baseCosts[0]
        def dfs(i: int, cost: int):
            nonlocal ans
            if abs(cost - target) < abs(ans - target) or (abs(cost - target) == abs(ans - target) and cost < ans):
                ans = cost
            if i == len(toppingCosts) or cost > target + abs(ans - target):
                return
            dfs(i + 1, cost)
            dfs(i + 1, cost + toppingCosts[i])
            dfs(i + 1, cost + 2 * toppingCosts[i])
        for b in baseCosts:
            dfs(0, b)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn closest_cost(base: Vec<i32>, t: Vec<i32>, target: i32) -> i32 {
        fn dfs(t: &Vec<i32>, i: usize, cost: i32, target: i32, ans: &mut i32) {
            if (cost - target).abs() < (*ans - target).abs() || ((cost - target).abs() == (*ans - target).abs() && cost < *ans) {
                *ans = cost;
            }
            if i == t.len() || cost > target + (*ans - target).abs() { return; }
            dfs(t, i + 1, cost, target, ans);
            dfs(t, i + 1, cost + t[i], target, ans);
            dfs(t, i + 1, cost + 2 * t[i], target, ans);
        }
        let mut ans = base[0];
        for &b in &base {
            dfs(&t, 0, b, target, &mut ans);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    closestCost(baseCosts: number[], toppingCosts: number[], target: number): number {
        let ans = baseCosts[0];
        function dfs(i: number, cost: number) {
            if (Math.abs(cost - target) < Math.abs(ans - target) || (Math.abs(cost - target) === Math.abs(ans - target) && cost < ans))
                ans = cost;
            if (i === toppingCosts.length || cost > target + Math.abs(ans - target)) return;
            dfs(i + 1, cost);
            dfs(i + 1, cost + toppingCosts[i]);
            dfs(i + 1, cost + 2 * toppingCosts[i]);
        }
        for (const b of baseCosts) dfs(0, b);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(3^m * n), where m is the number of toppings and n is the number of bases.
  • 🧺 Space complexity: O(m), recursion stack.