22.Generate Parentheses

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

例如, 给出 n = 3, 生成结果为:

[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

analyze

回溯法:

思路: 标记可使用的左括号和右括号数量, 中断条件为左右可使用括号数都为 0

• 若可使用的左括号的数量等于可使用的右括号的数量, 则加 '(';
• 若可使用的左括号的数量为 0, 则加 ')';
• 若可使用的左括号的数量小于可使用的右括号的数量, 则可以加 '(' 又可以加 ')'

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  const result = []
  let str = ''
  function judege(left, right, str) {
    if (left === 0 && right === 0) {
      result.push(str)
      str = ''
      return
    }

    if (left === right) {
      judege(left - 1, right, str + '(')
    } else if (left === 0) {
      judege(left, right - 1, str + ')')
    } else {
      judege(left - 1, right, str + '(')
      judege(left, right - 1, str + ')')
    }
  }

  judege(n, n, str)
  return result
};