## 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:

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


### 代码1

// Generate Parentheses
// 时间复杂度O(TODO)，空间复杂度O(n)
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
string path;
if (n > 0) generate(n, path, result, 0, 0);
return result;
}
// l 表示 ( 出现的次数, r 表示 ) 出现的次数
void generate(int n, string& path, vector<string> &result, int l, int r) {
if (l == n) {
string s(path);
result.push_back(s.append(n - r, ')'));
return;
}

path.push_back('(');
generate(n, path, result, l + 1, r);
path.pop_back();

if (l > r) {
path.push_back(')');
generate(n, path, result, l, r + 1);
path.pop_back();
}
}
};


### 代码2

// Generate Parentheses
// @author 连城 (http://weibo.com/lianchengzju)
class Solution {
public:
vector<string> generateParenthesis (int n) {
if (n == 0) return vector<string>(1, "");
if (n == 1) return vector<string> (1, "()");
vector<string> result;

for (int i = 0; i < n; ++i)
for (auto inner : generateParenthesis (i))
for (auto outer : generateParenthesis (n - 1 - i))
result.push_back ("(" + inner + ")" + outer);

return result;
}
};