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时，就可以放置新的左括号。当右括号出现次数小于左括号出现次数时，就可以放置新的右括号。

代码：第一种解法是当左括号有n个时，补n-r个右括号。

 1 class Solution {
 2 public:
 3     vector<string> generateParenthesis(int n) {
 4     vector<string> ans;
 5     if (n>0) generator(ans, "", 0, 0, n);
 6     return ans;
 7 }
 8 
 9 void generator(vector<string> & ans, string s, int l, int r, int n) { // r/l: appearance of ) (
10     if (l == n) {
11         ans.push_back(s.append(n-r, ')'));
12         return;
13     }
14     generator(ans, s+'(', l+1, r, n);
15     if (l>r) generator(ans, s+")", l, r+1, n);
16 }
17 };

第二种解法是当搜索深度达到2n时储存