balanced parentheses

  task is to generate all combinations of balanced parentheses.

Example 1:

Input:
N = 3
Output:
((()))
(()())
(())()
()(())
()()()
Example 2:
Input:
N = 1
Output:
()


c++ implementation:

void par(int o,int c,string opt)
    {
       if(o==0 && c==0) // leaf node
       {
           cout<<opt<<endl;
           return;
       }
       if(o!=0)     //open can be always used except when open =0
       {
           string opt1=opt;
           opt1=opt1+'(';
           par(o-1,c,opt1);
       }
       if(c>o)   //close paranthesis should be used only when close<open
       {
           string opt2=opt;
           opt2=opt2+')';
           par(o,c-1,opt2);
       }
    }
    vector<string> AllParenthesis(int n) 
    {
        string opt="";
        par(n,n,opt);
        vector<string>s;
        return s;
    }


Time Complexity: O(2^n). 
space Complexity: O(n) 
darkmode