How backtracking is used in this

#1

how we can use backtracking in this?

Generate parenthesis
#2

You have to print every possible result. So backtracking can be helpful.
Say n=2
You can get (()) as a possible result
Then you backtrack and can get ()() also as a possible result.
So after appending each parenthesis, backtrack to check other possibilities.
Check the code:

vector<string>result;
void parenthesis(int ob,int cb,int n,string str)
{
if(cb==n)//Base case
{
  result.push_back(str);//Push the result
  return;   
}
if(cb<ob)//When no of closing bracket is less than opening bracket , you can append )
 {
  str.append(")");
  parenthesis(ob,cb+1,n,str);
  str.pop_back();//Backtrack
 }
if(ob<n) //When no of opening brackets is less than n you can append (
 {
  str.append("(");
  parenthesis(ob+1,cb,n,str);
  str.pop_back();//Backtrack
 }
  return; 
}
#3

https://ide.codingblocks.com/s/214446 in this i havnt done any backtracking but how it is running fine and can u explain your code as i didnt know from which bracket function call backtracking is done firstly

#4

i am not able to dry run it plz help

#5

how it is making different types of patterns??

#6

Yes your approach is correct, you can do it without backtracking.

#7

i think it is overwriting the position with other char

#8

Yes…just as you backtrack in the problem to generate different permutations of string. You swap 2 charcters and then you again swap it back to its correct position after recursive call. Here also you push a character and then backtrack by popping it.