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

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

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

1<= n <= 8

方法

暴力法

回溯法

思路
一个「合法」括号组合的左括号数量一定等于右括号数量，这个显而易见。
对于一个「合法」的括号字符串组合p，必然对于任何0 <= i < len(p)都有：子串p[0..i]中左括号的数量都大于或等于右括号的数量。(通俗一点的意思是说：从左往右算的话，肯定是左括号多嘛，到最后左右括号数量相等，说明这个括号组合是合法的。)
其实总体思路也只有一句话，优先选择左括号，只有右括号比左括号剩的多，才去选择右括号；当总数够了就退出
算法

  1. /**
  2.  * @param {number} n
  3.  * @return {string[]}
  4.  */
  5. var generateParenthesis = function (n) {
  6.   let res = [];
  7.   // 用leftRemain记录还可以使用多少个左括号，用rightRemain记录还可以使用多少个右括号
  8.   const backtrack = (leftRemain, rightRemain, str) => {
  9.     // 左右括号所剩的数量，str是当前构建的字符串
  10.     if (str.length == n * 2) return res.push(str);
  11.     // 只要左括号有剩，就可以选它，然后继续做选择（递归）
  12.     if (leftRemain > 0) backtrack(leftRemain - 1, rightRemain, str + "(");
  13.     // 只有右括号比左括号剩的多，才能选右括号
  14.     if (rightRemain > leftRemain)
  15.       backtrack(leftRemain, rightRemain - 1, str + ")");
  16.   };
  17.   // 递归的入口，剩余数量都是n，初始字符串是空串
  18.   backtrack(n, n, "");
  19.   return res;
  20. };

按括号序列的长度递归

  1. /**
  2.  * @param {number} n
  3.  * @return {string[]}
  4.  */
  5. let generateParenthesis = function (n) {
  6.   if (n == 0) return [];
  8.   let data = new Map();
  9.   data.set(0, ['']);
  11.   for (let i = 1; i <= n; i++) {
  12.     let result = [];
  13.     for (let j = 0; j <= i - 1; j++) {
  14.       let center = data.get(j);
  15.       let right = data.get(i - 1 - j);
  16.       for (let k = 0; k < center.length; k++) {
  17.         for (let t = 0; t < right.length; t++) {
  18.           result.push(`(${center[k]})${right[t]}`);
  19.         }
  20.       }
  21.     }
  22.     data.set(i, result);
  23.   }
  24.   return data.get(n);
  25. };

⭐️广度优先搜索（BFS + 去重）

思路
总体思路是：从n-1推导出n的组合情况，只需要遍历n-1的所有组合，并在所有组合的每个位置填入一对括号()并去重即可。
举个例子：

  • n=1时，组合情况仅一种：[“()”]
  • n=2时

遍历 n=1 的组合情况 [“()”]
对于情况 “()”，在该字符串每个位置填入一对括号 () 后得到：[“()()”,”(())”,”()()”]
去重得到最终组合情况为：[“()()”,”(())”]

  • n=3时

遍历 n=2 的组合情况 [“()()”,”(())”]
对于情况 “()()”，在每个位置填入一对括号 () 后得到：[“()()()”,”(())()”,”()()()”,”()(())”,”()()()”]
对于情况 “(())”，在每个位置填入一对括号 () 后得到：[“()(())”,”(()())”,”((()))”,”(()())”,”(())()”]
去重得到最终组合情况为：[“()()()”,”(())()”,”()(())”,”(()())”,”((()))”]
算法

  1. /**
  2.  * @param {number} n
  3.  * @return {string[]}
  4.  */
  5. var generateParenthesis = function (n) {
  6.     let set = new Set(['()']);
  7.     for (let c = 2; c <= n; c++) {
  8.         let nextSet = new Set();
  9.         for (const s of set) {
  10.             for (let j = 0; j <= s.length; j++) {
  11.                 nextSet.add(s.slice(0, j) + '()' + s.slice(j));
  12.             }
  13.         }
  14.         set = nextSet;
  15.     }
  16.     return [...set];
  17. };

20220417： 执行用时：64 ms, 在所有 JavaScript 提交中击败了62.99%的用户 内存消耗：42.2 MB, 在所有 JavaScript 提交中击败了36.87%的用户 通过测试用例：8 / 8

知识点

  • 每个位置传入一个（）：set.add(s.slice(0, j) + ‘()’ + s.slice(j))

⭐️⭐️ 深度优先搜索

  1. var generateParenthesis = function (n) {
  2.     const res = []
  3.     const DFS = function (lBrackt, rBracket, str) {
  4.         if (str.length === 2 * n) {
  5.             res.push(str)
  6.             return
  7.         }
  9.         if (lBrackt > 0) {
  10.             DFS(lBrackt - 1, rBracket, str + "(")
  11.         }
  13.         if (lBrackt < rBracket) {
  14.             DFS(lBrackt, rBracket - 1, str + ")")
  15.         }
  16.     }
  18.     DFS(n, n, "")
  19.     return res
  20. };

20220417： 执行用时：56 ms, 在所有 JavaScript 提交中击败了92.14%的用户 内存消耗：41.3 MB, 在所有 JavaScript 提交中击败了74.53%的用户 通过测试用例：8 / 8