Closest Dessert Cost LeetCode solution in Java

1
class Solution {
2
  /** Closest cost result */
3
  int closestCost = Integer.MAX_VALUE;
4

5
  /** Difference between closest cost result and target so far */
6
  int closestCostDiff = Integer.MAX_VALUE;
7

8
  public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
9
    for (int base : baseCosts) {
10
      dfs(toppingCosts, 0, base, target);
11
    }
12
    return closestCost;
13
  }
14

15
  public void dfs(int[] toppingCosts, int toppingIndex, int cost, int target) {
16
    int costDiff = Math.abs(target - cost);
17
    if (costDiff < closestCostDiff || (costDiff == closestCostDiff && cost < closestCost)) {
18
      closestCostDiff = costDiff;
19
      closestCost = cost;
20
    }
21

22
    // Since toppings are all positive cost, stop dfs early if cost exceeds target
23
    if (toppingIndex >= toppingCosts.length || cost > target) return;
24

25
    dfs(toppingCosts, toppingIndex + 1, cost, target);
26
    dfs(toppingCosts, toppingIndex + 1, cost + toppingCosts[toppingIndex], target);
27
    dfs(toppingCosts, toppingIndex + 1, cost + 2 * toppingCosts[toppingIndex], target);
28
  }
29
}