31 lines
899 B
C++
31 lines
899 B
C++
#include "s0022_generate_parentheses.hpp"
|
|
|
|
// 深度优先遍历:
|
|
// 接收参数为每个节点的状态
|
|
// 遍历结果可以用指针放在接收参数保存，也可以通过声明一个 class 的成员来保存
|
|
void S0022::dfs(string current, int left, int right, vector<string> &result) {
|
|
// 讨论边界条件（结束条件）
|
|
// 不必讨论起始条件，因为初始化的工作会在 dfs 函数外完成。
|
|
if (left == 0 && right == 0) {
|
|
result.push_back(current);
|
|
}
|
|
// 讨论越界或不合法状态，剪枝
|
|
if (left > right) {
|
|
return;
|
|
}
|
|
// 合法状态，扩展到下一层
|
|
if (left > 0) {
|
|
dfs(current + '(', left - 1, right, result);
|
|
}
|
|
if (right > 0) {
|
|
dfs(current + ')', left, right - 1, result);
|
|
}
|
|
}
|
|
|
|
vector<string> S0022::generateParenthesis(int n) {
|
|
// 初始化
|
|
vector<string> result = {};
|
|
dfs("", n, n, result);
|
|
return result;
|
|
}
|