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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
解法: backtracking + 递归, 直接套用backtracking的模板解法.
1 class Solution { 2 public: 3 vector<string> generateParenthesis(int n) { 4 vector<string> allsol; 5 string sol; 6 7 gp(n, 0, 0, sol, allsol); 8 return allsol; 9 } 10 11 void gp(int n, int nleft, int nright, string& sol, vector<string>& allsol) { 12 if (nleft == n && nright == n){ 13 allsol.push_back(sol); 14 return; 15 } 16 17 if (nleft < n){ 18 sol.push_back(‘(‘); 19 gp(n, nleft+1, nright,sol, allsol); 20 sol.pop_back(); 21 } 22 23 if (nleft > nright){ 24 sol.push_back(‘)‘); 25 gp(n, nleft, nright+1, sol,allsol); 26 sol.pop_back(); 27 } 28 29 return; 30 } 31 };
[LeetCode] 22. Generate Parentheses
原文：http://www.cnblogs.com/amadis/p/5926547.html