问题
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
例子
given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
分析
dfs，递归地生成合法的字符串，生成规则如下：
- 如果(的数量 < n，加入(
- 如果(的数量 > )的数量，加入)
要点
dfs
时间复杂度
O(n!)，由于不会生成不合法的字符串，所以真实的时间复杂度要更小一点。
空间复杂度
O(n)
代码
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
string str;
generateParenthesis(res, str, 0, 0, n);
return res;
}
private:
void generateParenthesis(vector<string> &res, string str, int open, int close, int n) {
if (str.size() == n << 1) {
res.push_back(str);
return;
}
if (open < n)
generateParenthesis(res, str + "(", open + 1, close, n);
if (open > close)
generateParenthesis(res, str + ")", open, close + 1, n);
}
};
