<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> generateParenthesis(int n) {
        // brute force algorithm
        vector<string> combinations;

        // do a BFS using a queue to see possible combinations
        queue<string> q;
        q.push("");
        while(!q.empty())
        {
            string cur_string = q.front();
            q.pop();
            // check if the length of string reaches 2 * n since there are n pairs
            if(cur_string.length() == 2 * n)
            {
                // a string is valid when the amount of left parentheses match the right
                int left_count = 0;
                bool is_valid = true;
                for(int x = 0; x < cur_string.length(); x++)
                {
                    if(cur_string[x] == '(')
                    {
                        left_count++;
                    }
                    else
                    {
                        left_count--;
                    }
                    if(left_count < 0)
                    {
                        is_valid = false;
                        break;
                    }
                }
                if(left_count == 0 && is_valid == true)
                {
                    combinations.push_back(cur_string);
                }
                continue;
            }
            // append ")" and "(" to a string to a queue 
            q.push(cur_string + "(");
            q.push(cur_string + ")");
        }

        return combinations;
    }
};
26980