# Closest Dessert Cost
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/closest-dessert-cost)
Canonical: https://scaleengineer.com/dsa/problems/closest-dessert-cost
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Array
---
## 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._

**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] <= 104`
* `1 <= target <= 104`

# Approaches
## Backtracking with Recursion
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    int result;
    int target;

    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        this.result = baseCosts[0];
        this.target = target;
        for (int base : baseCosts) {
            dfs(toppingCosts, 0, base);
        }
        return result;
    }

    private void dfs(int[] toppingCosts, int index, int currentCost) {
        int currentDiff = Math.abs(currentCost - target);
        int resultDiff = Math.abs(result - target);

        if (currentDiff < resultDiff || (currentDiff == resultDiff && currentCost < result)) {
            result = currentCost;
        }

        // Base case and pruning
        if (index == toppingCosts.length || currentCost > target && currentCost > result) {
            return;
        }

        // Recursive calls for the next topping
        // Choice 1: 0 of current topping
        dfs(toppingCosts, index + 1, currentCost);
        // Choice 2: 1 of current topping
        dfs(toppingCosts, index + 1, currentCost + toppingCosts[index]);
        // Choice 3: 2 of current topping
        dfs(toppingCosts, index + 1, currentCost + 2 * toppingCosts[index]);
    }
}
```
### 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.

## Dynamic Programming
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        int maxCost = 30000; // A safe upper bound for cost
        boolean[] possible = new boolean[maxCost + 1];
        
        for (int base : baseCosts) {
            if (base <= maxCost) {
                possible[base] = true;
            }
        }
        
        for (int topping : toppingCosts) {
            // We can add each topping up to two times.
            // We run the loop twice to simulate adding one or two toppings.
            // The backward iteration prevents using the same topping unit multiple times in one go.
            for (int i = 0; i < 2; i++) {
                for (int cost = maxCost; cost >= topping; cost--) {
                    if (possible[cost - topping]) {
                        possible[cost] = true;
                    }
                }
            }
        }
        
        int result = Integer.MAX_VALUE;
        int minDiff = Integer.MAX_VALUE;
        
        for (int cost = 1; cost <= maxCost; cost++) {
            if (possible[cost]) {
                int diff = Math.abs(cost - target);
                if (diff < minDiff) {
                    minDiff = diff;
                    result = cost;
                } else if (diff == minDiff) {
                    result = Math.min(result, cost);
                }
            }
        }
        return result;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
private
  List<Integer> arr = new ArrayList<>();
private
  int[] ts;
private
  int inf = 1 << 30;
public
  int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
    ts = toppingCosts;
    dfs(0, 0);
    Collections.sort(arr);
    int d = inf, ans = inf;
```

### JavaScript

```javascript
const 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 ; };
```

### CPP

```cpp
class Solution {
public:
  const int inf = INT_MAX;
  int closestCost(vector<int> &baseCosts, vector<int> &toppingCosts,
                  int target) {
    vector<int> arr;
    function<void(int, int)> dfs = [&](int i, int t) {
      if (i >= toppingCosts.size()) {
        arr.push_back(t);
        return;
      }
      dfs(i + 1, t);
      dfs(i + 1, t + toppingCosts[i]);
    };
    dfs(0, 0);
    sort(arr.begin(), arr.end());
    int d = inf, ans = inf;
```

### Python

```python
class Solution:
    # 选择一种冰激淋基料 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 ans
    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

```