LeetCode: Closest Dessert Cost Solution

Approach

Exhausive search through all possibilities of topping (0, 1, 2) for each

Implementation

1function recursion(cost, toppingCosts, toppingCostsIdx, target, ref) {
2  if (toppingCostsIdx === toppingCosts.length) {
3    const diff = Math.abs(target - cost)
4    if (diff <= ref.minDiff) {
5      ref.cost = diff === ref.minDiff ? Math.min(ref.cost, cost) : cost
6      ref.minDiff = diff
7    }
8  } else {
9    recursion(
10      cost + toppingCosts[toppingCostsIdx] * 0,
11      toppingCosts,
12      toppingCostsIdx + 1,
13      target,
14      ref
15    )
16    recursion(
17      cost + toppingCosts[toppingCostsIdx] * 1,
18      toppingCosts,
19      toppingCostsIdx + 1,
20      target,
21      ref
22    )
23    recursion(
24      cost + toppingCosts[toppingCostsIdx] * 2,
25      toppingCosts,
26      toppingCostsIdx + 1,
27      target,
28      ref
29    )
30  }
31}
32
33/**
34 * @param {number[]} baseCosts
35 * @param {number[]} toppingCosts
36 * @param {number} target
37 * @return {number}
38 */
39var closestCost = function (baseCosts, toppingCosts, target) {
40  const ref = { minDiff: Infinity, cost: Infinity }
41  for (const baseCost of baseCosts) {
42    recursion(baseCost, toppingCosts, 0, target, ref)
43  }
44  return ref.cost
45}