<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>

#define faster \
ios::sync_with_stdio(false); \
cin.tie(nullptr);\
cout.tie(nullptr);

vector<string> parenthesis;
class Solution {
public:
    void dp(int no, int nc, int cur_length, string s)
    {
        if(nc > no || nc > cur_length || no > cur_length || (no+nc) > cur_length)
        {
            return;
        }

        if(s.length() == cur_length && nc == no)
        {
            parenthesis.push_back(s);
        }

        dp(no+1, nc, cur_length, s+'(');
        dp(no, nc+1, cur_length, s+')');
    }
    vector<string> generateParenthesis(int n) {
        faster
        parenthesis.clear();
        dp(0, 0, n*2, "");
        return parenthesis;
    }
};
32448