Skip to main content

括号生成

Tips

题目类型: BackTracking

题目​

给出 n 代表生成括号的对数, 请你写出一个函数, 使其能够生成所有可能的并且有效的括号组合.

提示:
  • 1 <= n <= 8
示例

输入: 3

输出: ['((()))', '(()())', '(())()', '()(())', '()()()']

题解​

如果要生成 n 对括号, 那需要 n 个左括号(left) 和 n 个右括号(right). 因此有以下规则:

  1. 对于每个合法的子串 track, 都要保证 left >= right. 比如说 (() 和 (), 用掉的左括号的数量大于或等于右括号的数量, 因此对于剩下的, 一定就是 left <= right, 所以如果出现了 right < left, 一定不符合.
  2. 在递归中如果剩下的 left 或者 right 小于 0 了, 一定也不符合, 比如 n 是 3, 如果 left 用掉了 4 次(即此时 left 是 -1), 那一定不能生成合法括号.
  3. 当 left 和 right 剩下的都恰好为 0 时, 是一个合法括号.
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  const res = []

  const dfs = (left, right, track) => {
    // 对于每个合法的 track 子串, 都要保证 left >= right, 即剩下的是 left <= right, 反之不合法
    if (right < left) return

    // 如果两边括号用掉的次数超过 n, 也是不合法的
    if (left < 0 || right < 0) return

    // 当两边括号剩下都恰好为 0 了, 证明是一个合法的括号生成
    if (left === 0 && right === 0) {
      res.push(track.join(''))
      return
    }

    track.push('(')
    dfs(left - 1, right, track)
    track.pop()

    track.push(')')
    dfs(left, right - 1, track)
    track.pop()
  }

  dfs(n, n, [])

  return res
}