Parenthesis Generate using Backtracking

Given Parenthesis size N, we have to generate all possible Parenthesis Of length N. One length = (), Two lengths = ()(),(())

Suppose N = 3,

Possible parenthesis are,

((())), (())(), ()(()), ()()(), (()())

Approach:
Easy to understand that, if we add n open brackets '(', then obviously we have to add n close brackets ')' also.

So, somehow we have to keep track of these two things. Now, what can be our base case? if we add n '(' brackets and n ')' brackets then simply we can add the string to our answer and return.

Our recursion code will look like this

void para(int l, int r, vector<string>&ans, string s){

        if(l == 0 and r==0){

            ans.push_back(s);

            return;

        }

        else{

            if(l > 0){

                para(l-1, r, ans, s+'(');

            }

            if(r > l){

                para(l, r-1, ans, s+')');

            }

        }

    }

We can start from " para(n, n, ans, s) " here. Initially, we pass n open and n close brackets, a string vector(ans), and an empty string s.

For better understanding take a pen and paper and illustrate this stuff.


You can submit your solution here.