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

    vector<string> generateSub(int remainingOpen, int remainingClose)
    {
        if (remainingOpen == 0)
        {
            return vector<string>{std::string(remainingClose, ')')};
        }

        vector<string> res;
        if (remainingOpen > 0)
        {
            vector<string> subString = generateSub(remainingOpen - 1, remainingClose + 1);
            for (auto const& elem : subString)
            {
                res.push_back("(" + elem);
            }
        }

        if (remainingClose > 0)
        {
            vector<string> subString = generateSub(remainingOpen, remainingClose - 1);
            for (auto const& elem : subString)
            {
                res.push_back(")" + elem);
            }
        }

        return res;
    }

    vector<string> generateParenthesis(int n) 
    {
        return generateSub(n, 0);
    }
};
19083