|C++| backtracking with explanation
Lets say we have to add toppings to a base say base_i\n\nthere are 3 ways to add toppings:\n1)add one topping to the base_i\n2)add 2 toppings to base_i\n3)add n
Lets say we have to add toppings to a base say base_i\n\nthere are 3 ways to add toppings:\n1)add one topping to the base_i\n2)add 2 toppings to base_i\n3)add no toppings to a base_i\nwe can easily implement this with recursion since we have 3 choices at each instant.\n\nWe will take now a particular base and start adding toppings to it by the above ways\n\nAlso i have made a utility function(closest()) that takes in 2 arguments and tells the closest among them to target.\n\nPlease do upvote if you liked,it gives me lot of motivation.\nAlso comment what you couldn\'t understand\n```\nclass Solution {\npublic:\n    int target;\n    int closest(int a,int b){ \n        if(a==0)\n            return b;\n        if(b==0)\n            return a;\n        if(abs(target-a)==abs(target-b))\n            return a<b?a:b;\n        return abs(target-a)<abs(target-b)?a:b;\n    }\n    \n    int dfs(vector<int>&top,int i,int sum){\n        if(i>=top.size())\n            return sum;\n\n        int a=dfs(top,i+1,sum+top[i]);\n        int b=dfs(top,i+1,sum+(top[i]*2));\n        int c=dfs(top,i+1,sum);\n        sum=closest(a,closest(b,c));\n        return sum;\n    }\n    \n    int closestCost(vector<int>& base, vector<int>& top, int t) {\n        target=t;//i made target global so that i don\'t need to pass it in any function\n        int ans=0;\n        for(int i=0;i<base.size();i++){\n            ans = closest(dfs(top,0,base[i]),ans);\n        } \n        return ans;\n    }\n};\n
[]