Back to Backtracking

Backtracking is concept to build a solution using recursion,going through all possible states and rejecting the state which did not satisfy the constraints till we reach the final goal state.

For understanding this we will solve problem name:

Generate all N matched parentheses.

INPUT is :Integer N
OUTPUT is :String of parentheses “(“ or “)”..the string should be balanced
by BALANCED I mean(number of “(“ open== number of “)” brackets)
So for input:

N=1 output is [“ () “]
{note 1: opening should be before closing}

N=2 output is [ “ (()) “,” ()() “]
{note 2: we have to print all possible solution permutation}

N=3 output is [“ ((())) “,” (())() “,” ()()() “, “ (()()) “,”()(()) “]

**The three key to recursion**

1. Our Choice
   {either use ( or ) }
2. Our constraints
   {we can not use “)” before “(“}
3. Our Goal
   {total 2*N character should be used {N ->” ( “ } + {N -> “)” } }

now we move step by step to solve the problem for N=3

When the number of open “(“ bracket is zero we start decreasing count of closing brackets “)” or when open < close

We gonna approach by taking input N and using a recursive function Back_track() with Parameter:

(number of “(”, number of “)”,Empty string which will be filled in each recursion step with either ( or ), vector of string to store the filled strings set)

class Solution {
public:
void Back_track(int open,int close,string bracket,vector<string>&v){
if(open==0 && close==0)
{
v.push_back(bracket);
return;
}
if(open>0){
Back_track(open-1, close, bracket + ’(‘ , v );
}
if(open<close){
Back_track(open , close-1 , bracket + ’)’ , v );
}

}

vector<string> generateParenthesis(int n) {

string bracket=””;
int open=n,close=n;
vector<string>v;
Back_track(open,close,bracket,v);
return v;

}
};