C# | Recursion with Time and space complexity explanation
Feel free to correct me if my Time and Space complexity analysis is wrong.\n\n\n\n/*\nInput: baseCosts = [2,3], toppingCosts = [4,5,100], target = 18\nOutput: C
Feel free to correct me if my Time and Space complexity analysis is wrong.\n\n```\n\n/*\nInput: baseCosts = [2,3], toppingCosts = [4,5,100], target = 18\nOutput: Closest possible cost to given target.\n\n\nExplanation:\n    - Explore all combinations and identify closest of all\n    - Take each base[i] and add it running current cost - O(n)\n    - for the choosen base[i], we have following choices\n        Base:\n            //update closest cost if there are two possible they want samllest\n            (target-current) < (target-result) || (target-current) == (target-result) && current < result (smallest)\n                result = current;\n        index == topping.length // no need to explore more\n            return;\n\n        - No topping[i] => explore with topping[i+1] and same current           -choice 1\n        - 1 topping[i] => explore with topping[i+1] and current + topping[i]    - choice 2\n        - 2 topping[i] => explore with topping [i+1] and current + 2 * topping[i] - choice 3\n    \n    time: O(n* (1+1+1)^m) => O(n* 3^m)\n    space: recursion stack could go upto size m => O(m)\n*/\n\n\npublic class Solution {\n    int result = 0;\n    public int ClosestCost(int[] baseCosts, int[] toppingCosts, int target) {\n        result = baseCosts[0];\n        foreach(var cost in baseCosts){\n            ChooseToppings(cost, 0, toppingCosts, target);\n        }\n        return result;\n    }\n    \n    private void ChooseToppings(int current, int start, int[] toppingCosts, int target){\n       \n        if (Math.Abs(target - current) < Math.Abs(target - result) || \n            (Math.Abs(target - current) == Math.Abs(target - result) && current < result))\n            result = current;\n        \n        if(start == toppingCosts.Length)\n            return;\n        \n        ChooseToppings(current, start+1, toppingCosts, target);\n        ChooseToppings(current + toppingCosts[start], start+1, toppingCosts, target);\n        ChooseToppings(current + 2* toppingCosts[start], start+1, toppingCosts, target);\n    }\n}\n\n```
['Depth-First Search']