<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) {
        /*
            Rules:
            1. More ones on the left
            2. At most N ones per number
        */
        vector<string> result;
        for (int i = 0; i < 65536; ++i) {
            bitset<16> bits(i);
            if (bits.count() != n) {
                continue;
            }

            int count = 0;
            for (int j = 0; j < n * 2; ++j) {
                count += bits[j] ? 1 : -1;
                if (count < 0) {
                    break;
                }
            }
            if (count == 0) {
                result.push_back(toString(bits, n*2));
            }
        }
        return result;
    }
    
    string toString(bitset<16> bits, int size) {
        string str(size, ')');
        for (int j = 0; j < size; j++) {
            if (bits[j]) {
                str[j] = '(';
            }
        }
        return str;
    }
};
8451