1774. Closest Dessert Cost (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        self.result = baseCosts[0]
        def dfs(cur, i):
            diff, pre_diff = abs(cur - target), abs(self.result - target)
            if diff < pre_diff or diff == pre_diff and cur < self.result:
                self.result = cur
            if cur - target > self.result:
                return
            if i < len(toppingCosts):
                dfs(cur, i + 1)
                dfs(cur + toppingCosts[i], i + 1)
                dfs(cur + toppingCosts[i] * 2, i + 1)
        for num in baseCosts:
            dfs(num, 0)
        return self.result