#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;
}