**B**acktracking is a concept to build a solution using recursion,going through all states and rejecting the state which did not satisfy the constraints.

for understanding 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 **“)”** closing brackets)

So for input N:::

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:

**Back_track**( number of **“(”** opening bracket

, number of* **“)”** closing bracket ,

* Empty string* which will be filled in each recursion step with either

**( or )**

**vector**of string to store the filled strings )**

*:::::::::::::::::::CODE:::::::::::::::::::::::::::::::::*

class Solution {

public:

void Back_track(int open,int close,string& bracket,vector&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; } };`