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<string> 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<string> ret; 26 };
LeetCode OJ：Generate Parentheses（括号生成）
原文：http://www.cnblogs.com/-wang-cheng/p/4976606.html