[leetcode]Generate Parentheses

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:

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

题目是要生成所有的匹配的括号序列：左括号和右括号的数目都为n，序列的任意位置index之前(左边的)的左括号总数都是要大于或者等于右括号总数。

总的序列的数目应该是卡特兰数：h(n)=C(2n,n)/(n+1) (n=0,1,2,...)或者h(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,...)

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string>
 4 #include <vector>
 5 using namespace std;
 6 
 7 
 8 
 9 void help(int total, int left, int right, string str, vector<string>& svec)
10 {
11     if(left>total || right>total || right>left)
12         return;
13     if(total==right&&left==total)
14     {
15         svec.push_back(str);
16         return;
17     }
18     else
19     {
20         if(left<total)
21             help(total, left+1, right, str+"(", svec);
22         if(right<left&&left<=total)
23             help(total, left, right+1, str+")", svec);
24     }
25 }
26 
27 
28 vector<string> generateParenthesis(int n) {
29     vector<string> svec;
30     help(n, 0, 0, "", svec);
31     
32     return svec;
33 }
34 
35 
36 
37 int main()
38 {
39     vector<string> svec;
40     svec=generateParenthesis(3);
41 }