Java || Backtracking explained in detail || TC & SC explained
// We need to check ALL the combinations of ALL the bases (1 base in one icre cream) with ALL the toppings (multiple toppings can go in one icre cream) with eac
// We need to check ALL the combinations of ALL the bases (1 base in one icre cream) with ALL the toppings (multiple toppings can go in one icre cream) with each topping taken 0, 1 or 2 times\n\n// We would use recursion for trying out MULTIPLE toppings on one base and we repeat this process for ALL the base\n// Objective is to find the cost of the icre cream AS CLOSE AS POSSIBLE to the target so that means that if target is $10 and you are getting one combination which will cost $9.81 and one combination which costs $10.10 then in that case we will return $10.10 because this is closer to $10 than $9.81\n// But if we get two combination which costs $9.85 and $10.15 (basically same difference) then we need to return lower value so $9.85\n\n// TC : O(M * 3^N) -> M = size of baseCosts; N = size of toppingCosts; 3^N because at each step we will have ATMOST 3 options (0, 1 or 2) of each type\n// SC : O(M * 3^N) -> recursion stack\n```\nclass Solution {\n    int result;\n    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {\n        result = baseCosts[0]; // base value\n        \n        for(int baseCost : baseCosts) {\n            helper(baseCost, toppingCosts, target, 0);\n        }\n        \n        return result;\n    }\n    \n    private void helper(int currentCost, int[] toppingCosts, int target, int toppingIdx) {\n        \n        // update result\n        if(Math.abs(target - currentCost) < Math.abs(target - result) ||\n            (Math.abs(target - currentCost) == Math.abs(target - result) && currentCost <= result)) {\n            result = currentCost;\n        }\n        \n        //recursion exit condition\n        if(toppingIdx == toppingCosts.length || currentCost >= target) return;\n        \n        //recursion for 0, 1 & 2 toppings\n        helper(currentCost, toppingCosts, target, toppingIdx + 1);\n        \n        // if current cost + unit of present topping cost < target, then we can take 1 unit of this topping\n        if(currentCost < target) {\n            helper(currentCost + toppingCosts[toppingIdx], toppingCosts, target, toppingIdx + 1);\n        }\n        \n        // if current cost + 2 unit of present topping cost < target, then we can take 2 unit of this topping\n        if(currentCost + toppingCosts[toppingIdx] < target) {\n            helper(currentCost + toppingCosts[toppingIdx] * 2, toppingCosts, target, toppingIdx + 1);\n        }\n    }\n}\n```
[]