40 ms | faster than 100.00% | How to optimise | Recursion
How do we solve this? \n- Loop through the base, because 1 base have to be used. \n- Call recursive function \n- Take 3 possibilities into consideration \n\t1. 
### How do we solve this? \n- Loop through the base, because 1 base have to be used. \n- Call recursive function \n- Take **3 possibilities** into consideration \n\t1. Ignore the topping \n\t2. Take 1 quantity of topping \n\t3. Take 2 quantities of topping (you can\'t have more that 2)\n- Increment the index by **one** on every recursive call  \n- Take the `abs(target-cost)` to find the deviation from the target \n- If the particular deviation already exists, replace the cost if its lower \n \n```\n# 40 ms, faster than 100.00%\nclass Solution:\n    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:\n        dairy = {}\n        \n        def possibleprices(cost,ind):\n            if abs(target-cost) in dairy: \n                if dairy[abs(target-cost)] > cost:\n                    dairy[abs(target-cost)] = cost \n            else:\n                dairy[abs(target-cost)] = cost\n            if ind>=len(toppingCosts) or cost-target > min(dairy):\n                return\n            possibleprices(cost,ind+1)\n            possibleprices(cost+toppingCosts[ind],ind+1)\n            possibleprices(cost+(toppingCosts[ind]*2),ind+1)\n            \n        for base in baseCosts:\n            curCost = base \n            possibleprices(curCost,0)\n        return dairy[min(dairy)]\n```\n\n### Optimisation \n\n```\nif ind>=len(toppingCosts) or cost-target > min(dairy):\n\treturn\n``` \nHere is where the optimisation happens. \nThe second condition makes sure that the recursive call doesn\'t happen when the deviation goes beyond the minimum current deviation in the positive side. So more toppings can\'t help because it\'s only going to cost more. \n\nI hope you would have found it helpful. \uD83D\uDE01
['Recursion', 'Python']