How to approach to recursion- begineers || C++ easy to understand
Resources: https://github.com/AJAYKR00KJ/LeetCode_Solution\n\nHow to approach problem\n\nConstraints: Most Important Factor\n\n n == baseCosts.length\n m == top
***Resources: https://github.com/AJAYKR00KJ/LeetCode_Solution***\n\n**How to approach problem**\n\n**Constraints:** Most Important Factor\n\n* n == baseCosts.length\n* m == toppingCosts.length\n* 1 <= n, m <= 10\n* 1 <= baseCosts[i], toppingCosts[i] <= 104\n* 1 <= target <= 104\n\nFrom the problem we can clearly see that **we have to select few choices from given array** and we can see the constraints **1 <= n, m <= 10.**\n\n**NOTE:**``` Here Recursion came into existence ```\n\nSo, lets move to problem.\n\n**We are given 3 inputs.**\n1. **baseCosts** ***-> Array,*** We have to select only 1 **(Compoulsary)** from it.\n1. **toppingCosts** ***-> Array,*** We have to select only 0 or more toppingcost **(** but we can select same topping atmost 2 time **)** from it.\n2. **target** -> an integer representing your target price for dessert.\n\n**Aim:**  \nMake a dessert with a total cost as close to target as possible by **selecting 1 baseCost(Compoulsary)** and select only 0 or more toppingcost **(** but we can select same topping atmost 2 time **)** from it.\n\n**Algorithm:**\n``` Take each baseCost every time and select toppingCost and store ans which is closest to target```\n\n```\nclass Solution {\npublic:\n    \n    //ans-> store final result\n    //mn -> Current minimum difference b/w target and curr_price\n    int ans=INT_MAX,mn=INT_MAX;\n    \n    /*\n      i-> index of tc(toppingCosts)\n      curr -> current cost taken\n      tar -> Target cost\n    */  \n    \n    void find(int i,vector<int>& tc,int curr, int tar)\n    { \n        /*\n           if difference b/w current cost and target cost is \n           less than min difference , so we have to update ans \n           and min difference because we got closest to target\n        */\n        if(abs(curr-tar)<mn)\n        { \n            mn=abs(curr-tar);\n            ans=curr;\n        }\n        \n        /*\n           if difference b/w current cost and target cost is \n           equal to min difference , so we have to update ans \n           and takin minimum one as condition given in problem\n        */\n        if(abs(curr-tar)==mn) ans=min(ans,curr); \n        \n        /*\n           If we are going out of bound just return \n           because we will nothing get after here\n        */\n        if(i>=tc.size() || curr-tar>mn) return;\n        \n        \n        /*  Main interesting thing -> How to recurse */\n        /*\n            Just put all the required conditions\n            \n            NOTE: We have already taken 1 baseCosts, so left that\n                  We have to select from tc(toppingCosts)\n                  \n            In our question we have 3 conditon\n            1. Take ith toppingCosts and go for next (i+1)th toppingCost\n            2. Take ith toppingCosts 2 times and go for next (i+1)th toppingCost\n            3. We will not take ith toppingCosts and will select next ones\n        */\n        \n        //taking ith toppingCosts and moving to (i+1)th toppingCosts\n         find(i+1,tc,curr+tc[i],tar); \n        \n        //taking ith toppingCosts 2 times and moving to (i+1)th toppingCosts\n         find(i+1,tc,curr+2*tc[i],tar); \n        \n        //Without taking ith toppingCosts and move to (i+1)th toppingCosts for next one\n         find(i+1,tc,curr,tar); \n        \n        \n    }\n    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {\n        \n        //take each baseCost every time\n        for(auto x:baseCosts)\n        {\n            //taking ith baseCost and select toppingCosts\n            find(0,toppingCosts,x,target); \n        }\n        \n        //return closest to target answer\n        return ans;\n        \n    }\n};\n```\n\n**Time Complexity: O(n * 3^(m)), n -> baseCosts.length,m -> toppingCosts.length\nSpace Complexity: O(1) ,ignoring recursive stack**\n\n**Complexity Analysis**\n\nSo, the basic idea of the **complexity of recursive solutions depends on the base case** of the recursive solution.\nHere our base case is \n\n```f(i>=tc.size() || curr-tar>mn) return;```\n\nHere we will return our function if we reach the end of the size. And for every i we are calling our function 3 times\nSo, for i=0 we we call 3 times \n```\nfind(i+1,tc,curr+tc[i],tar);  \nfind(i+1,tc,curr+2*tc[i],tar);  \nfind(i+1,tc,curr,tar); \n```\nFor i=1, we are calling again 3 times, **NOTE: These three will be called for every 3 previous function calls**\n```\nfind(i+1,tc,curr+tc[i],tar);  \nfind(i+1,tc,curr+2*tc[i],tar);  \nfind(i+1,tc,curr,tar); \n```\n.\n.\n.\nFor i=m\n, we are calling again 3 times, **NOTE: These three will be called for every 3 previous (m-1) function calls**\n```\nfind(i+1,tc,curr+tc[i],tar);  \nfind(i+1,tc,curr+2*tc[i],tar);  \nfind(i+1,tc,curr,tar); \n```\n \n\n**just think like grandfather have 3 child, So, now all the three childs have 3 childs again and all these have 3 again**\n``` \n                  A\n           /     |    \\\n        A       A       A\n      / | \\    / | \\    / | \\\n    A A A      A A A    A A A\n```\n\nSo, total number of call will be **3^0 + 3^1 + 3^2 + ........ + 3^m** ,where **m is size of toppingCosts.length**\nSum of GP = **3^0 * (((3^m) -1 )/ (3-1))** = **((3^m) -1)/2** \u2245 **3^m**\n\nSo, for every  baseCosts.length we are calling the function, and  **baseCosts.length is n**,\n\n**So, overall time complexity is O(n * (3^m))**\n\n-----------------------------------------------------------------------------------------------------------\n\n**Please let me know if any improvement needed**\n\n-------------------------------------------------------------\n\n**Feel free to comment :)**\n\n**Hit \uD83D\uDC4D , if it was helpful**
['Backtracking', 'Depth-First Search', 'Recursion', 'C', 'C++']