22.括号生成

发表于 分类于 阅读次数：

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

示例 1：

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

示例 2：

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

解题思路

这是一道经典的回溯题目，考察对递归和回溯的理解。

核心思想

  • 使用回溯算法生成所有可能的括号组合
  • 通过限制条件确保生成的括号有效
  • 左括号数量不能超过n，右括号数量不能超过左括号

方法一：回溯法（推荐）

时间复杂度 O(4^n/√n)、空间复杂度 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const result = [];
    
    function backtrack(open, close, current) {
        // 如果当前字符串长度达到2n，添加到结果中
        if (current.length === 2 * n) {
            result.push(current);
            return;
        }
        
        // 如果左括号数量小于n，可以添加左括号
        if (open < n) {
            backtrack(open + 1, close, current + '(');
        }
        
        // 如果右括号数量小于左括号数量，可以添加右括号
        if (close < open) {
            backtrack(open, close + 1, current + ')');
        }
    }
    
    backtrack(0, 0, '');
    return result;
};

方法二：优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var generateParenthesis = function(n) {
    const result = [];
    
    function generate(open, close, str) {
        if (open === n && close === n) {
            result.push(str);
            return;
        }
        
        if (open < n) {
            generate(open + 1, close, str + '(');
        }
        
        if (close < open) {
            generate(open, close + 1, str + ')');
        }
    }
    
    generate(0, 0, '');
    return result;
};

方法三：动态规划法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var generateParenthesis = function(n) {
    const dp = new Array(n + 1).fill().map(() => []);
    dp[0] = [''];
    
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            for (const left of dp[j]) {
                for (const right of dp[i - 1 - j]) {
                    dp[i].push('(' + left + ')' + right);
                }
            }
        }
    }
    
    return dp[n];
};

方法四：使用Set去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var generateParenthesis = function(n) {
    if (n === 0) return [''];
    if (n === 1) return ['()'];
    
    const result = new Set();
    
    for (const str of generateParenthesis(n - 1)) {
        // 在每个位置插入新的括号对
        for (let i = 0; i <= str.length; i++) {
            result.add(str.slice(0, i) + '()' + str.slice(i));
        }
    }
    
    return Array.from(result);
};

解题要点

  1. 回溯法：

    • 使用递归生成所有可能的组合
    • 通过限制条件确保括号有效
    • 左括号数量 ≤ n，右括号数量 ≤ 左括号数量

  2. 有效括号的条件：

    • 左括号和右括号数量相等
    • 在任何位置，左括号数量 ≥ 右括号数量

  3. 时间复杂度：

    • 卡特兰数：C(2n,n)/(n+1)
    • 时间复杂度：O(4^n/√n)

面试要点

  • 高频考点：这道题是面试中的高频回溯题
  • 回溯算法：考察对递归和回溯的理解
  • 括号匹配：考察对有效括号的判断
  • 时间复杂度：了解卡特兰数的概念

相关题目

扩展思考

  1. 为什么使用回溯法？

    • 需要生成所有可能的组合
    • 通过限制条件剪枝，避免无效组合
    • 递归结构清晰，易于理解

  2. 时间复杂度分析

    • 卡特兰数：C(2n,n)/(n+1)
    • 时间复杂度：O(4^n/√n)
    • 空间复杂度：O(n)

  3. 动态规划思路

    • dp[i]表示i对括号的所有有效组合
    • 状态转移：dp[i] = ‘(‘ + dp[j] + ‘)’ + dp[i-1-j]

  4. 边界情况

    • n = 0：返回[‘’]
    • n = 1：返回[‘()’]
    • n = 2：返回[‘()()’, ‘(())’]

  5. 实际应用

    • 编译器语法分析
    • 数学表达式生成
    • 代码格式化

  6. 变种问题

    • 生成不同长度的括号
    • 生成带权重的括号
    • 生成特定模式的括号

最后更新: 2021-09-27