22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

/**
 * 回溯 + 剪枝
 * 时间复杂度：O(?)
 * 空间复杂度：O(n)
 */
var generateParenthesis = function (n) {
  if (!n) return []
  if (n === 1) return ['()']
  const res = []
  function dfs(left, right, str) {
    if (str.length === 2 * n) {
      res.push(str)
      return
    }
    // 剪枝处理
    if (left > 0) {
      dfs(left - 1, right, str + '(')
    }
    if (right > left) {
      dfs(left, right - 1, str + ')')
    }
  }
  // n 代表剩余括号数量
  dfs(n, n, '')
  return res
}