跳到主要内容

剑指 Offer II 085.生成匹配的括号

· 阅读需 2 分钟

1、题干​

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

 

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]

 

提示：

  • 1 <= n <= 8

 

注意：本题与主站 22 题相同： https://leetcode-cn.com/problems/generate-parentheses/

2、解题思路​

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


3、举个例子​

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

4、代码​

var generateParenthesis = function (n) {
    let set = new Set(['()']);
    for (let c = 2; c <= n; c++) {
        let nextSet = new Set();
        for (const s of set) {
            for (let j = 0; j <= s.length; j++) {
                nextSet.add(s.slice(0, j) + '()' + s.slice(j));
            }
        }
        set = nextSet;
    }
    return [...set];
};

5、执行结果​

image.png