Skip to content

1774. Closest Dessert Cost 👍

  • Time: $O(n \cdot 3^m)$
  • Space: $O(n \cdot 3^m)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts,
                  int target) {
    int ans = INT_MAX;

    for (const int baseCost : baseCosts)
      dfs(toppingCosts, 0, target, baseCost, ans);

    return ans;
  }

 private:
  void dfs(const vector<int>& toppingCosts, int i, int target, int currCost,
           int& ans) {
    if (abs(currCost - target) < abs(ans - target))
      ans = currCost;
    if (i == toppingCosts.size() || currCost >= target)
      return;

    for (int k = 0; k < 3; ++k)
      dfs(toppingCosts, i + 1, target, currCost + k * toppingCosts[i], ans);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
    for (final int baseCost : baseCosts)
      dfs(toppingCosts, 0, target, baseCost);
    return ans;
  }

  private int ans = Integer.MAX_VALUE;

  private void dfs(int[] toppingCosts, int i, int target, int currCost) {
    if (Math.abs(currCost - target) < Math.abs(ans - target))
      ans = currCost;
    if (i == toppingCosts.length || currCost >= target)
      return;

    for (int k = 0; k < 3; ++k)
      dfs(toppingCosts, i + 1, target, currCost + k * toppingCosts[i]);
  }
}