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

示例 1：
输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

示例 2：
输入：n = 1
输出：[“()”]

提示：

  • 1 <= n <= 8

解题思路

因为之前有做过一题判断括号合法性的题目，所以一开始的想法是，我生成所有可能性的组合，然后判断这些组合中合法的放入结果数组中即可，那么这个题目就转为如何生成所有对应数量括号的组合和检查这些组合是否合法。

  1. 那么如何生成全部对应数量括号的组合呢？
n = 0, result = []
n = 1, result = ['(', ')']
n = 2, result = ['((', '()', ')(', '))']
n = 3, result = ['(((', '(()', '()(', '())', ')((', ')()', '))(', ')))']
...
可以看出一个规律，n+1的组合就是在n组合的基础上后面加上一个'('或者')'

代码可以写为:

let n = 3
let result = []

function generateAll(current) {
  //当前组合已经满足长度要求时，将组合合并成字符串添加到结果中
  if (current.length === 2 * n) {
    result.push(current.join(""))
  }else {
    //在当前组合的后面添加一个'('，继续向下遍历
    current.push('(')
    generateAll(current)
    current.pop()
    //上一种情况走完之后，回溯到父节点，在当前组合的后面添加一个')'，继续向下遍历
    current.push(')')
    generateAll(current)
    current.pop()
  }
}

generateAll([])
  1. 如何检查生成的组合是否合法

将左括号视为1，右括号视为-1，按照组合内字符的顺序进行加减，如果过程中出现值小于0，那么说明在没有与之匹配的左括号的情况下添加了右括号，视为不合法。遍历完发现如果值不等于0，说明左括号和右括号的数量不相等，那么也不合法。

代码可以写为:

function valid() {
  let balance = 0
  for (let i = 0; i < current.length; i++) {
      if (current[i] == '(') {
          ++balance
      } else {
          --balance
      }
      if (balance < 0) {
          return false
      }
  }
  return balance == 0
}

代码优化

上面两件事分开做，导致了时间消耗变多，可以在生成组合的过程中就进行合法性校验，而不是全部生成完毕之后，根据合法规则去进行过滤。

var generateParenthesis = function(n) {
    const ans = []  //存放结果的数组
    const current = [] //当前组合字符的数组

    function generate(open) {  //open代表左括号的个数
        if (current.length === n * 2) {  //如果当前字符组合的长度已经满足数量要求的话，就将其添加到结果中
            ans.push(current.join(""))
            return
        }
        if (open < n) { //如果当前可以添加左括号的话，就添加左括号。左括号的数量需要小于等于n
            current.push('(') //添加了左括号后，进行更深层的遍历
            generate(open + 1) 
            current.pop() //遍历结束后，回溯到父节点，查看添加右括号是否满足条件
        }

        if (current.length - open < open) { //current.length - open 表示当前已经添加的右括号的数量，右括号的数量需要满足小于等于左括号的数量
            current.push(')') //添加了右括号后，进行更深层的遍历
            generate(open)
            current.pop()
        }
    }
    generate(0)
    return ans
};