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:

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

思路:两个递归函数,互相调用

class Solution {public:    vector
     
       generateParenthesis(int n) {        if(n==0) return ret;                dfsLeft("",0,0,n);        return ret;    }        void dfsLeft(string s, int depthLeft, int depthRight, int n){ //add one left parenthesis        if(depthLeft >= n){ //end left            return;        }        else{            s += '(';            depthLeft++;            dfsRight(s,depthLeft, depthRight, n);            dfsLeft(s,depthLeft, depthRight, n);        }    }       void dfsRight(string s, int depthLeft, int depthRight, int n){ //add one right parenthesis        if(depthRight >= n){ //end all            ret.push_back(s);        }        else if(depthRight >= depthLeft){ //end right            return;        }        else{            s += ')';            depthRight++;            dfsLeft(s,depthLeft, depthRight, n);            dfsRight(s,depthLeft, depthRight, n);        }    }private:    int len;    vector
      
        ret;};
      
     

更简洁的写法：

class Solution {public:    vector
     
       generateParenthesis(int n) {        if(n == 0) return ret;                len = n*2;        dfsLeft(n, 0, "");        return ret;    }        void dfsRight(int lNum, int rNum, string str){
   //add right parenthese        while(rNum){             str += ')';            dfsLeft(lNum, --rNum, str);        }        if(str.length() == len){            ret.push_back(str);        }    }        void dfsLeft(int lNum, int rNum, string str){
   //add left parenthese        while(lNum){            str += '(';            dfsRight(--lNum, ++rNum, str);        }    }private:    int len;    vector
      
        ret;};