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
};