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:

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

 求出所有可能的括号组合，在dfs加上回溯条件，右括号数目不能超过左括号，还有就是左括号数最大不能超过n，代码如下：

1 class Solution { 2 public: 3     vector
     
       generateParenthesis(int n) { 4         dfs(0,n*2,0,0,""); 5         return ret; 6     } 7  8     void dfs(int dep, int maxDep, int left, int leftTotal, string curr){ 9         if(leftTotal*2 > maxDep)10             return;11         if(dep == maxDep){12             ret.push_back(curr);13             return;14         }15         for(int i = 0; i < 2; i++){16             if(i == 0){17                 dfs(dep+1, maxDep, left+1, leftTotal+1, curr+"(");18             }else{19                 if(left)20                     dfs(dep+1, maxDep, left-1, leftTotal, curr+")");21             }22         }23     }24 private:25     vector
      
        ret;26 };