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 generateParenthesis(int n) { 4 string tmpres(n<<1, '('); 5 vector res; 6 helper(1, tmpres, res, n-1, n); 7 return res; 8 } 9 private:10 void helper(int index, string &tmpres, vector &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 else24 {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 generateParenthesis(int n) { 4 string tmpres; 5 vector res; 6 helper(tmpres, res, n, n); 7 return res; 8 } 9 private:10 void helper(string &tmpres, vector &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 };
【版权声明】转载请注明出处：