22 括号生成
递归版
如果左括号数小于对数,选择左括号
如果右括号个数小于左括号,选择右括号
class Solution {
private:
void dfs(vector<string>& ans, string& res, int left, int right, int n) {
if (res.size() == n * 2) {
ans.push_back(res);
return;
}
if (left < n) {
res.push_back('(');
dfs(ans, res, left + 1, right, n);
res.pop_back();
}
if (right < left) {
res.push_back(')');
dfs(ans, res, left, right + 1, n);
res.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
string res;
dfs(ans, res, 0, 0, n);
return ans;
}
};