<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:
    std::vector<std::string> generateParenthesis(int n) {
        std::vector<std::string> res;
        std::unordered_set<std::string> parSet;
        if(n > 0)
        {
            std::queue<std::string> parQueue;
            parQueue.push("()");
            int size = parQueue.size();
            int remain = n-1;
            while(remain > 0)
            {
                std::string& frontStr = parQueue.front();
                for(int i = 0; i <= frontStr.size(); i++)
                {
                    if(i==0)
                    {
                        std::string temp = "()"+frontStr;
                        if(parSet.find(temp)==parSet.end())
                        {
                            parQueue.push(temp);
                            parSet.insert(temp);
                        }
                    }else if(i == frontStr.size())
                    {
                        std::string temp = frontStr+"()";
                        if(parSet.find(temp) == parSet.end())
                        {
                            parQueue.push(temp);
                            parSet.insert(temp);
                        }

                    }else{
                        std::string leftStr = frontStr.substr(0, i);
                        std::string rightStr = frontStr.substr(i, frontStr.size()-i);
                        std::string newStr = leftStr+"()"+rightStr;
                        if(parSet.find(newStr) == parSet.end())
                        {
                            parQueue.push(newStr);
                            parSet.insert(newStr);
                        }
                    }
                }
                parQueue.pop();
                size--;
                if(size == 0)
                {
                    remain--;
                    size = parQueue.size();
                }
            }
            while(!parQueue.empty())
            {
                res.push_back(parQueue.front());
                parQueue.pop();
            }
        }
        return res;
    }
};

10578