Python: Explained Easy Backtracking with Time and Space complexity
Just by looking at the constrains 1<=n,m<=10 we can say that this problem can be easily solved using backtracking.\n\nIdea: Generate all possible solutions, In 
Just by looking at the constrains 1<=n,m<=10 we can say that this problem can be easily solved using backtracking.\n\nIdea: Generate all possible solutions, In the below given fashion.\n![image](https://assets.leetcode.com/users/images/83d5ebfb-aa16-43bd-b2cd-92cec29623c8_1623817992.6077542.png)\n\nI hope this recursive idea makes sense!\n\nLet n = number of bases and m = number of toppings\nTime = O(n) for base and O(3^m) for toppings as each toppings has three possibilities (0,1,2)  = O(n * 3^m).\nSpace = O(3^n) for a ternary tree (3-way recursive stack).\n\nThe Full code:\n```\nclass Solution:\n    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n        self.ans = self.diff = float(\'inf\')\n        \n        n = len(baseCosts)\n        m = len(toppingCosts)\n        \n        \n        def solve(sum, target, indx):\n            if abs(sum - target) < self.diff:\n                self.diff = abs(sum - target)\n                self.ans = sum\n            elif abs(sum - target) == self.diff:\n                self.ans = min(self.ans, sum)\n            \n            \n            if indx == m:\n                return\n            \n            i = indx\n            for count in range(3):\n                sum += toppingCosts[i]*count\n                solve(sum,target,i+1)\n                sum -= toppingCosts[i]*count\n        \n        for i in baseCosts:\n            solve(i, target, 0)\n        return self.ans\n```\n
['Backtracking', 'Python']