1774. Closest Dessert Cost | 1702

 1class Solution:
 2    def closestCost(
 3        self, baseCosts: List[int], toppingCosts: List[int], target: int
 4    ) -> int:
 5        # intuition
 6        # not straightforward but we can break things down
 7        # base only
 8        # base + 1x topping A
 9        # base + 2x topping A
10        # base + 1x topping A + 1x topping B
11        # base + 1x topping A + 2x topping B
12        # ...
13        # we can append toppingCosts with 2x each topping
14        # and keep toppingCosts sorted
15        # then for each base, binary search
16        # this will not work because we cannot have both 1xstrawberry and 2xstrawberry
17        # ... brute force? brute force works but it's not what we wanted to practice
18        # backtracking huh
19
20        closest_possible_cost = baseCosts[0]
21        n, m = len(baseCosts), len(toppingCosts)
22
23        def update_best(candidate) -> bool:
24            nonlocal closest_possible_cost
25            # True means meaningful update
26            # False means way overblown, no need to continue
27            # print(candidate, closest_possible_cost)
28
29            candidate_diff = abs(candidate - target)
30            running_diff = abs(closest_possible_cost - target)
31            if candidate_diff < running_diff or (
32                candidate_diff == running_diff and candidate < closest_possible_cost
33            ):
34                closest_possible_cost = candidate
35                return True
36            elif candidate >= closest_possible_cost >= target:
37                return False
38            return True
39
40        def dfs(current_cost: int, current_topping_idx: int) -> None:
41            # print(current_cost, current_topping_idx)
42            # update & exit check
43            # if current_topping_idx >= m or not update_best(current_cost):
44            #     return
45            # above is a SERIOUS BUG!!!
46            if not update_best(current_cost) or current_topping_idx >= m:
47                return
48
49            for number_of_current_topping in range(3):
50                dfs(
51                    current_cost
52                    + number_of_current_topping * toppingCosts[current_topping_idx],
53                    current_topping_idx + 1,
54                )
55
56            return
57
58        for i in range(n):
59            update_best(baseCosts[i])
60            if closest_possible_cost == target:
61                return target
62            dfs(baseCosts[i], 0)
63
64        return closest_possible_cost