22.括号生成

括号生成

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

示例 1：

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

示例 2：

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

示例 3：

输入：n = 2
输出：[“()()”,”(())”]

提示：

• 1 <= n <= 8

解析

/**
 * @param {number} n
 * @return {string[]}
 */
// 合法括号的两个特征
// 1. 字符串任意前缀 左括号 >= 右括号
// 2. 左右括号数量相等
var generateParenthesis = function (n) {
  const result = [];

  function dfs(leftNum, rightNum, n, combine) {
    // 结束条件
    if (leftNum + rightNum === 2 * n) {
      result.push(combine);
      return;
    }
    // 添加左括号
    if (leftNum < n) {
      dfs(leftNum + 1, rightNum, n, combine + "(");
    }
    // 添加右括号
    if (rightNum < n && leftNum > rightNum) {
      dfs(leftNum, rightNum + 1, n, combine + ")");
    }
  }

  dfs(0, 0, n, "");
  return result;
};