Hey everyone , I hope you all are doing fine and are healthy. I have struggled with Backtracking for the better part of my coding , cause even though the answers are available, and resources are available, no one that I found was willling enough to explain the intuition and concept behind it, and to judge the method to do it.
Here , in this post, I am going to try and post some questions related to B.T. and below that I will share the code and a link. The link is for those who would like to see a detailed solution, and they can visit that. I want to keep this article short, so that those looking for the answer directly don't have to go past all the explanation part for each question, while also not compromising others who want to see a detail analysis .
So, lets get right into it.
I.) Backtracking problems: There are multiple problems available on LC for practicing B.T., but these are the ones I would like to recommend to go through first before handling others:
1.) Letter Combinations of a Phone Number
2.)Generate Parentheses
3.)Permutations
4.)Permutations II
5.)Combinations
6.)Subsets
7.)Subsets II
8.)N-Queens
II.)Solutions:
- Letter Combinations of a Phone Number :
Code:
class Solution {
public:
vector<string>result;
void helper(string digits,int index,string current)
{
vector<string>v= {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // to generate string for that index
if(index==digits.length()) //base case
{
result.push_back(current);
return;
}
string s=v[digits[index]-'0'];
for(int i=0;i<s.length();i++)
{
// If some letter remaining to consider, consider that and generate the combination or go to base case and end recursion for that letter
helper(digits,index+1,current+s[i]);
}
}
vector<string> letterCombinations(string digits) {
if(digits=="") return {};
helper(digits,0,"");
return result; //return answer
}
};For Detail Solution: Solution
- Generate Parentheses
Code:
class Solution {
public:
vector<string>result;
void helper(int open,int close,int n,string current)
{
if(current.length()==n*2) // base case
{
result.push_back(current);
return;
}
// If opening are less than n, hence generate combination with one more opening
if(open<n) helper(open+1,close,n,current+"(");
// If closing are less than n, hence generate combination with one more closing as conditions are met
if(close<open) helper(open,close+1,n,current+")");
}
vector<string> generateParenthesis(int n) {
helper(0,0,n,"");
return result;
}
};For Detail Solution: Solution
- Permutations
Code:
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> output; // to hold result
generatePermutations(nums, output, 0);
return output; // return answer
}
private:
void generatePermutations(vector<int> nums, vector<vector<int>>&output, int idx) {
if (idx == size(nums)) // base case
{
output.emplace_back(nums);
}
for (int i = idx; i < size(nums); ++i)
{
swap(nums[i], nums[idx]); // swap the current element with the next to get another permutation
generatePermutations(nums, output, idx + 1); // generate permutations for the next element
}
}
};For Detail Solution:Solution
- Permutations II
Code:
class Solution {
public:
vector<vector<int>>ans;
void helper(vector<int> nums,int idx)
{
if(idx==nums.size()) // base case
{
ans.push_back(nums);
}
for(int i=idx;i<nums.size();i++)
{
if(i!=idx && nums[i]==nums[idx]) continue;
swap(nums[i],nums[idx]);
helper(nums,idx+1);
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(),nums.end());
helper(nums, 0);
return ans;
}
};For Detail Solution:Solution
- Combinations
Code:
class Solution {
public:
vector<vector<int>> ans;
void helper(int idx, int k,vector<int>¤t,int n)
{
if(current.size()==k) // base case
{
ans.push_back(current);
return;
}
for(int i=idx;i<n+1;i++)
{
current.push_back(i); //consider the current element i
helper(i+1,k,current,n); // generate combinations
current.pop_back(); //proceed to next element
}
}
vector<vector<int>> combine(int n, int k) {
vector<int>current;
helper(1,k,current,n);
return ans; //return answer
}
};For Detail Solution: Solution
- Subsets
Code:
class Solution {
public:
vector<vector<int>>subset;
void helper(int index, vector<int>¤t,vector<int>&nums)
{
subset.push_back(current); // push the current subset into the resultant array
for(int i=index;i<nums.size();i++)
{
current.push_back(nums[i]); // add the current element to consider the subsets corresponding to it
helper(i+1,current,nums); //generate subsets for this array
current.pop_back(); // as this has been used, pop it
}
return;
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<int>current;
helper(0,current,nums);
return subset; //return answer
}
};For Detail Solution: Solution
- Subsets II
Code:
class Solution {
public:
set<vector<int>>subsets; // initialising set
void helper(int index,vector<int>¤t, vector<int>&nums)
{
subsets.insert(current); //inserting current array to the result
for(int i=index;i<nums.size();i++)
{
current.push_back(nums[i]); // add the current element to consider the subsets corresponding to it
helper(i+1,current,nums); //generate subsets for this array
current.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<int>current;
helper(0,current,nums);
vector<vector<int>>ans(subsets.begin(),subsets.end()); //make vector from set
return ans; //return answer
}
};For Detail Solution: Solution
- N-Queens
Code:
class Solution {
public:
vector<vector<string>>ans;
bool check(int row,int col,int n,vector<string>&curr) // A fn to check if a queen can be placed or not in a partcular row
{
for(int i=0;i<row;i++) //check the column
{
if(curr[i][col]=='Q')
return false;
}
for(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--) //check left diagonal
{
if(curr[i][j]=='Q')
return false;
}
for(int i=row-1,j=col+1;i>=0 && j>=0;i--,j++) //check right diagonal
{
if(curr[i][j]=='Q')
return false;
}
// If there is no queen placed in left, or right diagonal or in the same column, then place the queen by returning true
return true;
}
void helper(vector<string>& curr,int n, int row) // to generate all the possible combinations
{
if(row==n) // if we have reached the end for a particular column, push the current combination into the result and return
{
ans.push_back(curr);
return;
}
for(int col=0;col<n;col++) // We iterate over column and hence row ,left and right diagonal remain to be considered which we consider in check function
{
if(check(row,col,n,curr)) // If it can be placed
{
curr[row][col]='Q'; // place the queen in that particular row and column
helper(curr,n,row+1); // check the next row for placement
curr[row][col]='.'; //reset it for future column and row combinations
}
}
return;
}
vector<vector<string>> solveNQueens(int n) {
vector<string>curr(n,string(n,'.'));
helper(curr,n,0);
return ans; //return answer
}
};I hope you liked this post. I only considered doing it for 8 questions since I didn't know if this helps or not.
If it helped, please UPVOTE .
Also, I would keep updating this with more and more problems, if this turns out to be helpful .
Happy Coding and keep up the good work :)