Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

[Solution]

使用递归，从空字符串开始构造。

假设当前已经构造的是str, 剩余左右括号left, right：

如果left > 0, 说明还有左括号，可以直接加入左括号

如果left < right, 说明剩余右括号且个数大于左括号，可以放入右括号

1 vector
     
       generateParenthesis(int n)  2     { 3         vector
      
        result; 4         generate(result, "", n, n); 5          6         return result; 7     } 8      9     void generate(vector
       
         &result, string line, int left, int right)10     {11         if (left == 0 && right == 0)12         {13             result.push_back(line);14             return;15         }16         17         if (left > 0)18             generate(result, line + "(", left - 1, right);19         20         if (left < right)21             generate(result, line + ")", left, right - 1);22     }