<p>Given <code>n</code> pairs of parentheses, write a function to <em>generate all combinations of well-formed parentheses</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> n = 3
<strong>Output:</strong> ["((()))","(()())","(())()","()(())","()()()"]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> n = 1
<strong>Output:</strong> ["()"]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 8</code></li>
</ul>

class Solution {
public:
    void func(int open,int close,int n,int ind,vector<string> &see,string q){
        if(ind>2*n){
            return ;
        }
        if(ind==(2*n-1)){
            q+=')';
            see.push_back(q);
            return ;
        }
        else if(open>=n){
            q+=')';
            func(open,close+1,n,ind+1,see,q);
        }
        else if(close>=n){
            q+='(';
            func(open+1,close,n,ind+1,see,q);
        }
        else{
            string w=q;
            w+=')';
            func(open,close+1,n,ind+1,see,w);
            q+='(';
            func(open+1,close,n,ind+1,see,q);
        }
    }
    vector<string> generateParenthesis(int n) {
        vector<string> see;
        string q="(";
        func(1,0,n,1,see,q);
        vector<string> ans;
        for(int i=0;i<see.size();i++){
            int open=0;
            int close=0;
            int flag=1;
            for(int j=0;j<see[i].size();j++){
                if(see[i][j]=='('){
                    open++;
                }
                else{
                    close++;
                }
                if(close>open){
                    flag=0;
                    break;
                }    
            }
            if(flag && close==open){
                ans.push_back(see[i]);
            }
        }
        return ans;

    }
};
19386