Python 3 | Backtracking, DFS | Explanation
Explanation\n- There will be 10 bases at most and 10 toppings at most, you can choose among (0, 1, 2) amount of each topping type. In total, maximum, there will
### Explanation\n- There will be 10 bases at most and 10 toppings at most, you can choose among (0, 1, 2) amount of each topping type. In total, maximum, there will be `10 * (3 ^ 10) = 590490` combinations.\n- Since `590490` is less than `10^3 * 10^3` (experience), it\'s total doable to try out all `590490` combinations\n- Use backtracking to test out all the combination and find out the cloest one based on rules\n- `ans` is a tuple contains these information, `ans = (total_cost, absolute_difference, less/equal/greater_than_target)`\n- Starting with `[0] * m`, try out all possibilities\n### Implementation\n```\nclass Solution:\n    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n        m = len(toppingCosts)\n        ans = (baseCosts[0], abs(baseCosts[0]-target), -1 if target > baseCosts[0] else (0 if target == baseCosts[0] else 1))\n        \n        def dfs(cnt, cur_idx):\n            nonlocal ans, m, base \n            if cur_idx >= m: return\n            for i in range(3):\n                cnt[cur_idx] = i\n                if cur_idx >= m: return\n                s = sum([tc * c for tc, c in zip(toppingCosts, cnt)]) + base\n                diff = abs(target - s)\n                sign = -1 if target > s else (0 if target == s else 1)\n                if not diff: ans = (target, 0, 0); return\n                if diff < ans[1]: ans = (s, diff, sign)\n                elif diff == ans[1] and ans[2] == 1 and sign == -1: ans = (s, diff, sign)\n                dfs(cnt[:], cur_idx+1)\n            \n        for base in baseCosts:\n            dfs([0] * m, 0)\n        return ans[0]\n```
['Backtracking', 'Depth-First Search', 'Python', 'Python3']