括号生成

力扣🔗：https://leetcode-cn.com/problems/generate-parentheses (opens new window)

题目

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

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

解题思路

• 根据深度优先遍历算法做加法，从 '' 开始做加法，找出所有可能性。
• 递归生成树，使用变量 left 记录左括号使用个数，变量 right 记录右括号使用个数，变量 str 记录当前调用栈拼接的字符串。
• 当 left < n 时，即还有左括号可以使用时，可以添加左括号。
• 当 left < right 时，不可能是有效的括号组合，所有将其剪掉。
• 当 left > right 时，只有添加右括号才可能是有效的括号组合。

代码实现

/**
 * @param {number} n
 * @return {string[]}
 */
function generateParenthesis(n) {
  const result = []

  /**
   * @param {string} str 当前的括号字符串
   * @param {number} left str 中左括号个数
   * @param {number} right str 中右括号个数
   */
  function generator(str = '', left = 0, right = 0) {
    if (left === n && right === n) {
      // 左右括号个数都到上限 n 时
      result.push(str)
      return
    }

    if (left < right) return // 剪去左括号小于右括号的枝叶

    if (left < n) {
      // 左括号未到上限时，都可添加
      generator(str + '(', left + 1, right)
    }

    if (left > right) {
      // 左括号数量大于右括号时，添加右括号
      generator(str + ')', left, right + 1)
    }
  }

  generator()
  return result
}