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:

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

思路：

有关Parentheses的题目也是比较常见的，除了还有，

回溯用递归写是性价比最高的，基本思想就是从前往后填字符保证'('的个数不能比')'少，且'('的个数不能比n多

代码：

1 void generateAtDepth(vector
     
       &Parentheses, string &p, int lefts, int rights, int depth, int n){ 2     if(depth == 2*n-1){ 3         p[depth] = ')'; 4         Parentheses.push_back(p); 5         return;//返回值为void的函数不能忘了return啊！ 6     } 7     if(lefts < n){
   //注意不能出现((() 8         p[depth] = '('; 9         generateAtDepth(Parentheses, p, lefts+1, rights, depth+1, n);10     }11     if(lefts > rights){12         p[depth] = ')';13         generateAtDepth(Parentheses, p, lefts, rights+1, depth+1, n);14     }15 }16 vector
      
        generateParenthesis(int n) {17     vector
       
         Parentheses;18     if(n < 1) return Parentheses;19     string p(2*n, '*');//一定要指定初始化字符20     generateAtDepth(Parentheses, p, 0, 0, 0, n);21     return Parentheses;22 }