22. 括号生成

22. 括号生成

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

示例 1：
输入：n = 3 输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：
输入：n = 1 输出：[“()”]

提示：

• 1 <= n <= 8

思路

回溯法优先添加左括号，然后再添加右括号保证括号合法性

解答

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  const stack = [];
  const res = [];
  const dfs = (left, right) => {
    if (left === n && right === n) {
      res.push(stack.join(""));
      return res;
    }
    if (left < n) {
      stack.push("(");
      dfs(left + 1, right);
      stack.pop();
    }
    if (right < left) {
      stack.push(")");
      dfs(left, right + 1);
      stack.pop();
    }

    return res;
  };
  return dfs(0, 0);
};