General approach to backtracking problems in C++
Below I present a general approach to many standard backtracking problems. A similar version exists for JAVA here but I thought it would be a good idea to do th
Below I present a general approach to many standard backtracking problems. A similar version exists for JAVA [here](https://leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)) but I thought it would be a good idea to do the same for C++ as well, even though  the essence of the solutions remains the same. Most of these problems follow a single template as given below. \n\n```\n//Template\nvoid Backtrack(int start)\n{\n    //Base case \n\n// loop for all possible values\n{\n    //include the current element at this position if possible in the ans \n\t//More generally, make a choice \n\n    Backtrack(start+1) \n\n    //backtrack by removing current element \n}\n```\n\n\n**1**.[78. Subsets](https://leetcode.com/problems/subsets/)\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> subsets(vector<int>& a) {\n        vector<vector<int>> ans;\n        vector<int> subset;\n        n=a.size();\n        \n        GenerateSubs(a,0,subset,ans);\n        return ans;      \n    }\nprivate:\n    int n;\n    void GenerateSubs(vector<int>&a,int s,vector<int>&subset,vector<vector<int>>&ans)\n    {\n          for(int i=s;i<n;i++)\n        {\n            subset.push_back(a[i]); //include element at ith position\n            GenerateSubs(a,i+1,subset,ans); //generate all subsets including ith element\n            subset.pop_back(); //backtrack\n        }\n        ans.push_back(subset);\n    }\n};\n```\n\n**2**.[90. Subsets II](https://leetcode.com/problems/subsets-ii/) (Subsets with duplicates)\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> subsetsWithDup(vector<int>& a) {\n        vector<vector<int>> ans;\n        vector<int> subset;\n        n=a.size();\n        \n        sort(a.begin(),a.end()); //sort the elements so that we can keep track of duplicates\n        GenerateSubs(a,0,subset,ans);\n        return ans;    \n    }\nprivate:\n    int n;\n    void GenerateSubs(vector<int>&a,int s,vector<int>&subset,vector<vector<int>>&ans)\n    {\n        for(int i=s;i<n;i++)\n        {\n            if(i==s||a[i]!=a[i-1]) \n            {\n              subset.push_back(a[i]); //include element at ith position\n              GenerateSubs(a,i+1,subset,ans); //generate all subsets including ith element\n              subset.pop_back(); //backtrack\n            }\n        }\n        ans.push_back(subset);\n    }\n};\n```\n\n**3.** [77. Combinations](https://leetcode.com/problems/combinations/)\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> combine(int n, int k) {\n        vector<vector<int>> ans;\n        vector<int> combination;\n        \n        GenerateCombs(n,1,k,ans,combination);\n        return ans;\n    }\nprivate:\n    void GenerateCombs(int n,int s,int k,vector<vector<int>> &ans,vector<int> &combination)\n    {\n        if(combination.size()==k) //base case\n        {\n            ans.push_back(combination);\n            return;\n        }\n        \n        for(int i=s;i<=n;i++)\n        {\n            combination.push_back(i); //include i in a combination\n            GenerateCombs(n,i+1,k,ans,combination);\n            combination.pop_back(); //remove i, i.e. backtrack\n        }\n    }\n};\n```\n\n**4.** [39. Combination Sum\n](https://leetcode.com/problems/combination-sum/)\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> combinationSum(vector<int>& a, int sum) {\n        n=a.size();\n        sort(a.begin(),a.end()); // optimising by only including elements smaller than sum\n        combs(a,0,sum);\n        \n        return ans;\n        \n    }\nprivate:\n    vector<vector<int>>ans;\n    vector<int> combination;\n    int n;\n    \n    void combs(vector<int>&a,int s,int sum)\n    {\n        if(sum<0) //base case1\n            return;\n        \n        if(sum==0)\n        {\n            ans.push_back(combination); //base case 2\n            return;\n        }\n        \n        for(int i=s;i<n&&a[i]<=sum;i++)\n        {\n            combination.push_back(a[i]);\n            combs(a,i,sum-a[i]);\n            combination.pop_back();\n        }\n    }  \n};\n```\n\n**5.** [40. Combination Sum II\n](https://leetcode.com/problems/combination-sum-ii/)\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> combinationSum2(vector<int>& a, int sum) {\n        n=a.size();\n        sort(a.begin(),a.end()); // optimising by only including elements smaller than sum\n        combs(a,0,sum);\n        \n        return ans;\n        \n    }\nprivate:\n    vector<vector<int>>ans;\n    vector<int> combination;\n    int n;\n    \n    void combs(vector<int>&a,int s,int sum)\n    {\n        if(sum<0)\n            return;\n        \n        if(sum==0)\n        {\n            ans.push_back(combination);\n            return;\n        }\n        \n        for(int i=s;i<n&&a[i]<=sum;i++)\n        {\n                \n            if(i==s||a[i]!=a[i-1])\n            {\n             combination.push_back(a[i]);\n             combs(a,i+1,sum-a[i]);\n             combination.pop_back();   \n            }\n        }\n    }\n};\n```\n\n**6.**  [22. Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)\n```\nclass Solution {\npublic:\n    vector<string> generateParenthesis(int n) {\n        string s;\n        Generate(0,0,s,n);\n        return ans;\n    }\nprivate:\n    vector<string>ans;\n    void Generate(int left,int right,string &s,int n)\n    {\n        if(left==n&&right==n) // base case: when left and right parentheses are equal to n.\n        {\n            ans.push_back(s);\n            return;\n        }\n\t\t\n        // case I: if left parenteses are less than n, we can add a ( to the string. \n\t\t//But we might also add a ) so we backtrack by poppping it.\n        if(left<n)\n\t\t{\n            s+=\'(\';\n            Generate(left+1,right,s,n);\n            s.pop_back(); \n        }\n        \n        if(left>right) //case II: follows from I.\n        {\n            s+=\')\';\n            Generate(left,right+1,s,n);\n            s.pop_back();\n        } \n    }\n};\n```\n\n**7.** [131. Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning/)\n\n```\nclass Solution {\npublic:\n    vector<vector<string>> partition(string s) {\n        n=s.size();\n        Generate(s,0);\n        return ans;   \n    }\nprivate:\n    vector<vector<string>>ans;\n    vector<string>Partition;\n    int n;\n    \n    bool is_pal(string &s,int start,int end)\n    {\n        while(start<=end)\n        {\n            if(s[start++]!=s[end--])\n                return false;\n        }\n        return true;\n    }\n    \n    void Generate(string &s,int start)\n    {\n        if(start==n)\n        {\n            ans.push_back(Partition);\n            return;\n        }\n        \n        for(int i=start;i<n;i++)\n        {\n            if(is_pal(s,start,i))\n            {\n                Partition.push_back(s.substr(start,i-start+1));\n                Generate(s,i+1);\n                Partition.pop_back();\n            }\n        }\n    } \n};\n```\n\n**8.** [46. Permutations](https://leetcode.com/problems/permutations/)\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> permute(vector<int>& arr) {\n        vector<vector<int>> ans;\n        \n        permutations(arr,0,ans);\n        \n        return ans;\n    }\n    void permutations(vector<int>&arr,int s,vector<vector<int>>&ans)\n    {\n        if(s==arr.size())\n        {\n            ans.push_back(arr);\n            return;\n        }\n        for(int i=s;i<arr.size();i++)\n        {\n            swap(arr[s],arr[i]);\n            permutations(arr,s+1,ans);\n            swap(arr[s],arr[i]);\n        }\n    }\n};\n```\n\n\n
[]