<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:
    bool check(string s){
        stack<char>t;
        for(int i=0;i<s.size();i++){if(s[i]=='('){t.push(s[i]);}else{if(!t.empty()){t.pop();}else{return false;}}} return t.empty();
    }   
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string x=""; for(int i=0;i<n;i++){x=x+'(';} for(int i=0;i<n;i++){x=x+')';} ans.push_back(x);
        vector<int> s(n);
        for(int i=0;i<n;i++){s[i]=i;}
        while(true){ int i=n-1;
            while(s[i]==n+i){i--; if(i==-1)break;}
            if(i==-1)break;
            s[i]++; for(int j=i+1;j<n;j++){s[j]=s[j-1]+1;}
            string k=""; for(int i=0;i<2*n;i++){k=k+')';}
            for(int i=0;i<n;i++){k[s[i]]='(';} 
            if(check(k)){ans.push_back(k);}
        }
        return ans;

    }
};
26676