<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 isValid(string s) {
        stack<char> st;
        bool f = false;
        for (int i = 0; i < s.size();i++){
            if(s[i] == '{' || s[i] == '(' || s[i] == '['){
                f = false;
                if(s[i] == '[' ){
                st.push(']');
                // cout << 1 << endl;
            }
            if(s[i] == '{'){
                st.push('}');
                // cout << 2 << endl;
            }
            if(s[i] == '('){
                // cout << 3 << endl;
                st.push(')');
            }}
            else{
                // cout << s[i] << endl;
                if(!st.empty()){
                if(s[i] == st.top()){
                    // cout << st.top() << endl;
                    st.pop();
                    f = true;
                }else{
                    return false;
                }
                }else{
                    return false;
                }
            }
        }
        if(f && st.empty()){
        return true;
        }else{return false;}
    }

    vector<string> perms(string s) {
    vector<string> result;
    sort(s.begin(), s.end());
    do {
        result.push_back(s);
    } while (next_permutation(s.begin(), s.end()));
    return result;
    }
    vector<string> generateParenthesis(int n) {
        string s = "";
        int temp = n;
        while(temp--){
            s.push_back('(');
            s.push_back(')');
        }
        vector<string> result = perms(s);
        vector<string> ans;
        for(int i = 0; i < result.size(); i++){
            cout << result[i] << endl;
            if(isValid(result[i])){
                ans.push_back(result[i]);
            }
        }
        return ans;
    }
};
29410