13. 括号生成（22）

一、题目内容 中等

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

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

示例2：

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

提示：

• 1 <= n <= 8

  二、解题思路

  看到这个题，我就在想回溯，但是又很难想出具体步骤，我们来缕一缕。
  为什么要用回溯，三个括号，我先放左括号，那接下来放做还是右呢？我先放左嘛，放完 3 个左，就肯定要是((()))。好了，回退一个左括号，合上右括号，再放左括号，就是这样(())()。
  所以这就是为啥想用回溯。

那么怎么回溯呢，for 循环，好像用不着啊？那我回溯递归的时候，放几个左括号呢，n 个。那是不是就可以这样

const path = []
// left 代表，已经放入几个左括号
const backTracking = (left, right) => {
  if (left < n) {
    path.push('(')
    backTracking(left + 1, right)
    path.pop()
  }
}

那右括号呢？当我 path 有三个左括号(((，我就应该放三个右括号)))。
当我 path 有两个左括号((，我就应该放两个右括号))。接着再放入一个左括号时(())(，我得再加一个)

下面代码中，让 right < left，也保证了，括号生成后，肯定是合法的。不会出现类似()))的情况

const path = []
// left 代表，已经放入几个左括号
// right 代表，已经放入几个右括号
const backTracking = (left, right) => {
  if (left < n) {
    path.push('(')
    backTracking(left + 1, right)
    path.pop()
  }
  if (right < left) {
    path.push(')')
    backTracking(left, right + 1)
    path.pop()
  }
}

什么时候结束递归呢？肯定是指定了几个括号，path 满足条件之后就可以了

const path = []
const result = []
// right 代表，已经放入几个右括号
// left 代表，已经放入几个左括号
const backTracking = (left, right) => {
  // 结束递归
  if (path.length === n * 2) {
    result.push(path.join(''))
    return
  }
  // ...
}

三、具体代码

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  const result = []
  const path = []
  const backTracking = (left, right) => {
    if (path.length === n * 2) {
      result.push(path.join(''))
      return
    }
    if (left < n) {
      path.push('(')
      backTracking(left + 1, right)
      path.pop()
    }
    if (right < left) {
      path.push(')')
      backTracking(left, right + 1)
      path.pop()
    }
  }
  backTracking(0, 0)
  return result
};

四、其他解法