22.Generate Parentheses

22. Generate Parentheses

方法一：枚举当前位置填左括号还是右括号本质是「选或不选」的思想，你可以把填左括号视作「选」，填右括号视作「不选」。

从2n个位置中选n个位置放左括号（选等于放左括号，不选等于放右括号）

递归的过程中，要保证右括号的个数不能超过左括号的个数。

如果现在右括号个数等于左括号个数，那么不能填右括号。

如果现在右括号个数小于左括号个数，那么可以填右括号。

由于左括号个数始终 ≥ 右括号个数，且至多填 n 个左括号，所以当我们填了 n 个右括号时，也一定填了 n 个左括号，此时填完所有 2n 个括号。

path可以改成空数组，恢复现场

/**
 * 生成所有有效的 n 对括号组合
 * @param {number} n - 需要生成的括号对数
 * @return {string[]} - 包含所有有效括号组合的数组
 */
var generateParenthesis = function (n) {
  // 存储最终所有有效的括号组合结果
  const ans = []
  // 存储当前递归路径中的括号组合（临时路径）
  const path = []

  /**
   * 深度优先搜索（DFS）递归函数，用于构建有效括号组合
   * @param {number} left - 已使用的左括号数量
   * @param {number} right - 已使用的右括号数量
   */
  function dfs(left, right) {
    // 递归终止条件：当右括号数量等于n时，说明已生成一个完整的有效组合
    // 因为只有在合法的条件下才会添加右括号，所以此时path中的组合一定有效
    if (right === n) {
      // 将当前路径的括号数组拼接成字符串，加入结果数组
      ans.push(path.join(''))
      return // 结束当前递归分支
    }

    // 分支1：添加左括号（前提：已使用的左括号数量 < n）
    if (left < n) {
      path.push('(') // 将左括号加入当前路径
      dfs(left + 1, right) // 递归：左括号数量+1，右括号数量不变
      path.pop() // 回溯：移除刚添加的左括号，尝试其他分支
    }

    // 分支2：添加右括号（前提：已使用的右括号数量 < 左括号数量，保证组合有效）
    if (right < left) {
      path.push(')') // 将右括号加入当前路径
      dfs(left, right + 1) // 递归：右括号数量+1，左括号数量不变
      path.pop() // 回溯：移除刚添加的右括号，尝试其他分支
    }
  }

  // 初始化递归：左括号和右括号的初始数量都为0
  dfs(0, 0)
  // 返回最终的有效括号组合数组
  return ans
}

python

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        m = n * 2
        ans = []
        path = [''] * m
        def dfs(i, left):
            if i == m:
                ans.append(''.join(path))
                return
            # 选（选的条件）
            # 可以选左 left parenthesis can be chosen
            if left < n:
                path[i] = '('
                dfs(i+1, left+1)
            # 不选（右）（选择右边的条件）
            # 可以选右 right parenthesis can be chosen
            right = i - left
            if right < left:
                path[i] = ')'
                dfs(i+1, left)
        dfs(0, 0)
        return ans

方法一：枚举当前位置填左括号还是右括号(选或不选)

python

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        path = [''] * (n * 2)  # 所有括号长度都是 2n

        # 目前填了 left 个左括号，right 个右括号
        def dfs(left: int, right: int) -> None:
            if right == n:  # 填完 2n 个括号
                ans.append(''.join(path))
                return
            if left < n:  # 可以填左括号
                path[left + right] = '('  # 直接覆盖
                dfs(left + 1, right)
            if right < left:  # 可以填右括号
                path[left + right] = ')'  # 直接覆盖
                dfs(left, right + 1)

        dfs(0, 0)  # 一开始没有填括号
        return ans

作者：灵茶山艾府
链接：https://leetcode.cn/problems/generate-parentheses/solutions/2071015/hui-su-bu-hui-xie-tao-lu-zai-ci-pythonja-wcdw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：枚举下一个左括号的位置

python

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        path = []  # 记录左括号的下标

        # 目前填了 i 个括号
        # balance = 这 i 个括号中的左括号个数 - 右括号个数
        def dfs(i: int, balance: int) -> None:
            if len(path) == n:
                s = [')'] * (n * 2)
                for j in path:
                    s[j] = '('
                ans.append(''.join(s))
                return
            # 枚举填 right=0,1,2,...,balance 个右括号
            for right in range(balance + 1):
                # 先填 right 个右括号，然后填 1 个左括号，记录左括号的下标 i+right
                path.append(i + right)
                dfs(i + right + 1, balance - right + 1)
                path.pop()  # 恢复现场

        dfs(0, 0)
        return ans

作者：灵茶山艾府
链接：https://leetcode.cn/problems/generate-parentheses/solutions/2071015/hui-su-bu-hui-xie-tao-lu-zai-ci-pythonja-wcdw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。