22.括号生成

链接：22.括号生成
难度：Medium
标签：字符串、动态规划、回溯
简介：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

题解 1 - javascript

• 编辑时间：2020-04-09
• 执行用时：68ms
• 内存消耗：35.1MB
• 编程语言：javascript
• 解法介绍：通过集合去重，再递归判断括号内部。

/**
 * @param {number} n
 * @return {string[]}
 */
const cache = new Map();
cache.set(1, ['()']);
cache.set(2, ['()()', '(())']);
var generateParenthesis = function (n) {
  if (cache.has(n)) return cache.get(n);
  const res = new Set();
  for (let i = 1; i < n; i++) {
    for (let left of generateParenthesis(i))
      for (let right of generateParenthesis(n - i)) res.add(`${left}${right}`);
  }
  for (let item of generateParenthesis(n - 1)) res.add(`(${item})`);
  const arr = [...res];
  cache.set(n, arr);
  return arr;
};