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:
"((()))", "(()())", "(())()", "()(())", "()()()"
所有组合的个数其实是一个卡特兰数。
我们这样来构造一个合法的字符串：首先第一个位置肯定是“（”，对于后面位置:
1、如果前一个字符是“（”：那么我们可以在当前位置上加入“）”（字符“）”一定有剩余）；如果“（”字符还有剩余，也可以在当前位置加入“（” 本文地址
2、如果前一个字符是“）”：如果当前“（”和“）”剩余的数目不同（即其那面的括号没有完全匹配），可以在当前位置上加入“）”；如果“（”字符还有剩余，也可以在当前位置加入“（”
1 class Solution { 2 public: 3 vector<string> generateParenthesis(int n) { 4 string tmpres(n<<1, '('); 5 vector<string> res; 6 helper(1, tmpres, res, n-1, n); 7 return res; 8 } 9 private: 10 void helper(int index, string &tmpres, vector<string>&res, int leftNum, int rightNum) 11 { 12 if(index >= tmpres.size()){res.push_back(tmpres); return;} 13 if(tmpres[index-1] == '(') 14 { 15 tmpres[index] = ')'; 16 helper(index+1, tmpres, res, leftNum, rightNum-1); 17 if(leftNum > 0) 18 { 19 tmpres[index] = '('; 20 helper(index+1, tmpres, res, leftNum-1, rightNum); 21 } 22 } 23 else 24 { 25 if(leftNum != rightNum) 26 { 27 tmpres[index] = ')'; 28 helper(index+1, tmpres, res, leftNum, rightNum-1); 29 } 30 if(leftNum > 0) 31 { 32 tmpres[index] = '('; 33 helper(index+1, tmpres, res, leftNum-1, rightNum); 34 } 35 } 36 } 37 };
其实对于某个合法的字符串，我们可以发现从合法字符串的任何一个位置看，“（”的数目 >= ")"的数目，即剩余的“（”的数目 <= 剩余的"）"数目, 因此就有以下更加简洁的代码
1 class Solution { 2 public: 3 vector<string> generateParenthesis(int n) { 4 string tmpres; 5 vector<string> res; 6 helper(tmpres, res, n, n); 7 return res; 8 } 9 private: 10 void helper(string &tmpres, vector<string>&res, int leftNum, int rightNum) 11 { 12 if(leftNum > rightNum)return; 13 if(leftNum == 0 && rightNum == 0) 14 { 15 res.push_back(tmpres); 16 return; 17 } 18 if(leftNum > 0) 19 { 20 tmpres.push_back('('); 21 helper(tmpres, res, leftNum-1, rightNum); 22 tmpres.pop_back(); 23 } 24 if(rightNum > 0) 25 { 26 tmpres.push_back(')'); 27 helper(tmpres, res, leftNum, rightNum-1); 28 tmpres.pop_back(); 29 } 30 } 31 };
本文转自tenos博客园博客，原文链接：http://www.cnblogs.com/TenosDoIt/p/3776583.html，如需转载请自行联系原作者
