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

 

示例：

1
2
3
4
5
6
7
8
输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]
参考解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  const res = []
  dfs('', n, n, res)
  return res
};
/**
 * 深度遍历（回溯）
 */
function dfs (curStr, left, right, res) {
  // 当左括号、右括号剩余数均为0时终止递归
  if (left === 0 && right === 0) {
    res.push(curStr)
    return
  }
  // 当左括号剩余数大于右括号剩余数
  // 即，已使用的左括号数少于已使用的右括号数
  // 终止递归
  if (left > right) {
    return
  }
  if (left > 0) {
    dfs(curStr + '(', left - 1, right, res)
  }
  if (right > 0) {
    dfs(curStr + ')', left, right - 1, res)
  }
}

解题思路

深度优先（回溯）：

  1. 当前左右括号都有大于 0 个可以使用的时候，才产生分支；

  2. 产生左分支的时候，只看当前是否还有左括号可以使用；

  3. 产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；

  4. 在左边和右边剩余的括号数都等于 0 的时候结算。