Closest Dessert Cost LeetCode solution in C++

1
class Solution {
2
 public:
3
  // ans-> store final result
4
  // mn -> Current minimum difference b/w target and curr_price
5
  int ans = INT_MAX, mn = INT_MAX;
6

7
  /*
8
    i-> index of tc(toppingCosts)
9
    curr -> current cost taken
10
    tar -> Target cost
11
  */
12

13
  void find(int i, vector<int> &tc, int curr, int tar) {
14
    /*
15
       if difference b/w current cost and target cost is
16
       less than min difference , so we have to update ans
17
       and min difference because we got closest to target
18
    */
19
    if (abs(curr - tar) < mn) {
20
      mn = abs(curr - tar);
21
      ans = curr;
22
    }
23

24
    /*
25
       if difference b/w current cost and target cost is
26
       equal to min difference , so we have to update ans
27
       and takin minimum one as condition given in problem
28
    */
29
    if (abs(curr - tar) == mn) ans = min(ans, curr);
30

31
    /*
32
       If we are going out of bound just return
33
       because we will nothing get after here
34
    */
35
    if (i >= tc.size() || curr - tar > mn) return;
36

37
    /* Main interesting thing -> How to recurse */
38
    /*
39
        Just put all the required conditions
40

41
        NOTE: We have already taken 1 baseCosts, so left that
42
              We have to select from tc(toppingCosts)
43

44
        In our question we have 3 conditon
45
        1. Take ith toppingCosts and go for next (i+1)th toppingCost
46
        2. Take ith toppingCosts 2 times and go for next (i+1)th toppingCost
47
        3. We will not take ith toppingCosts and will select next ones
48
    */
49

50
    // taking ith toppingCosts and moving to (i+1)th toppingCosts
51
    find(i + 1, tc, curr + tc[i], tar);
52

53
    // taking ith toppingCosts 2 times and moving to (i+1)th toppingCosts
54
    find(i + 1, tc, curr + 2 * tc[i], tar);
55

56
    // Without taking ith toppingCosts and move to (i+1)th toppingCosts for next
57
    // one
58
    find(i + 1, tc, curr, tar);
59
  }
60
  int closestCost(vector<int> &baseCosts, vector<int> &toppingCosts, int target) {
61
    // take each baseCost every time
62
    for (auto x : baseCosts) {
63
      // taking ith baseCost and select toppingCosts
64
      find(0, toppingCosts, x, target);
65
    }
66

67
    // return closest to target answer
68
    return ans;
69
  }
70
};