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对括号的合法序列，那么有两个约束问题：
1.左括号和右括号成对，最终为n;
2.任一子序列均是左括号个数大于等于右括号的个数。
这个题目是求所有解的问题，我们先来看BFS的做法。
BFS：广度优先遍历。这个算法需要队列来将待运算的结点放入队列。我们的求解方法是先放左括号，压队；再放右括号，当右括号为N时，压入答案，否则压入队。由于先放左括号，再放右括号，且放左括号时判断了x<n,放右括号时判断了左括号数>右括号数。代码如下：
<span style="font-size:18px;">struct node{ int x,y; string now; }; class Solution { public: void help(int n,vector<string>&answer) { if(n==0) { answer.push_back(""); return; } node tmp; tmp.x=tmp.y=0; tmp.now=""; queue<node>q; for(q.push(tmp);!q.empty();q.pop()) { tmp=q.front(); node other; if(tmp.x<n) { other.x=tmp.x+1; other.y=tmp.y; other.now=tmp.now+"("; q.push(other); } if(tmp.x>tmp.y) { other.x=tmp.x; other.y=tmp.y+1; other.now=tmp.now+")"; if(other.y==n) { answer.push_back(other.now); } else { q.push(other); } } } } vector<string> generateParenthesis(int n) { vector<string>answer; help(n,answer); return answer; } };</span> DFS：本题使用DFS十分简单，因为从起点到终点一个方向增长下去。代码如下：
<span style="font-size:18px;">class Solution { public: void help(int n,int x,int y,string now,vector<string>&answer) { if(y==n) { answer.push_back(now); return; } if(x<n) { help(n,x+1,y,now+"(",answer); } if(x>y) { help(n,x,y+1,now+")",answer); } } vector<string> generateParenthesis(int n) { vector<string>answer; help(n,0,0,"",answer); return answer; } };</span>
