Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.（给定n对括号，编写一个函数来生成格式正确的括号的所有组合。）
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
1. 递归方法解决
class Solution {
public:
void generateParenthesisDFS(int left, int right, string out, vector<string> &vec) {
if (left > right) return;
if (left == 0 && right == 0) vec.push_back(out);
else {
if (left > 0) generateParenthesisDFS(left - 1, right, out + "(", vec);
if (right > 0) generateParenthesisDFS(left, right - 1, out + ")", vec);
}
}
vector<string> generateParenthesis(int n) {
vector<string> vec;
generateParenthesisDFS(n, n, "", vec);
return vec;
}
};
2. 另一种巧妙方法
class Solution {
public:
vector<string> generateParenthesis(int n) {
set<string> t;
if (n == 0) t.insert("");
else {
vector<string> pre = generateParenthesis(n - 1);
for (auto a : pre) {
for (int i = 0; i < a.size(); ++i) {
if (a[i] == '(') {
a.insert(a.begin() + i + 1, '(');
a.insert(a.begin() + i + 2, ')');
t.insert(a);
a.erase(a.begin() + i + 1, a.begin() + i + 3);
}
}
t.insert("()" + a);
}
}
return vector<string>(t.begin(), t.end());
}
};
参考链接：
