Backtracking - Extremely simple, elegant, and beats 98.58%. You will love this!
Intuition\nFind the minimum over all bases by running DFS over all toppings to find the choices which minimize the absolute difference to the total. We stop whe
# Intuition\nFind the minimum over all bases by running DFS over all toppings to find the choices which minimize the absolute difference to the total. We stop when adding more toppings will just take us further from the target as an optimiztion.\n\n\n# Code\n```\nclass Solution:\n    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n                \n        @cache\n        def solve(value, j=0):\n\n            if j == len(toppingCosts):\n                return value\n\n            # Pruning makes this really fast!\n            if value > target:\n                return value\n\n            return min( \n                    solve(value + 2 * toppingCosts[j], j + 1),\n                    solve(value + toppingCosts[j], j + 1),\n                    solve(value, j + 1),\n                    key = lambda x: (abs(target - x), x)\n                    )\n\n        return min([solve(base) for base in baseCosts], key = lambda x: (abs(target - x), x))\n        \n\n```
['Dynamic Programming', 'Backtracking', 'Depth-First Search', 'Python3']