跳到主要内容

括号生成

题目链接​

LeetCode 22 - 括号生成

题目​

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路​

这道题要求生成所有可能的有效括号组合。我们可以使用回溯算法来解决这个问题。回溯算法是一种通过递归遍历所有可能的解并构建有效解的方式。在构建过程中，我们会保持对左括号和右括号的计数，并且确保在任何时刻，右括号的数量都不超过左括号的数量，这样才能保证生成的是有效的括号组合。

具体步骤如下：

  1. 定义一个递归函数 backtrack，该函数接受当前生成的字符串 current 和两个计数器 left 和 right，分别表示当前剩余的左括号和右括号的数量。
  2. 在每次递归调用中，首先判断 current 的长度是否达到了 2 * n，如果达到了，说明我们生成了一个有效的组合，将其加入结果集。
  3. 如果 left 大于 0，我们可以放置一个左括号，然后递归调用 backtrack，将 left 减 1。
  4. 如果 right 大于 0 并且 right 大于 left，我们可以放置一个右括号，然后递归调用 backtrack，将 right 减 1。
  5. 递归结束时回溯到上一步，继续尝试其他可能的组合。

代码​

function generateParenthesis(n) {
    const result = [];
    
    function backtrack(current, left, right) {
        if (current.length === 2 * n) {
            result.push(current);
            return;
        }
        
        if (left > 0) {
            backtrack(current + '(', left - 1, right);
        }
        
        if (right > 0 && right > left) {
            backtrack(current + ')', left, right - 1);
        }
    }
    
    backtrack('', n, n);
    return result;
}

复杂度分析​

  • 时间复杂度：O(2n⋅n)O(2^n \cdot n)。对于每一个括号组合的生成，我们需要递归遍历所有可能的括号排列，而每个排列的长度为 n，因此时间复杂度是指数级的。
  • 空间复杂度：O(n)O(n)。递归调用栈的深度最多为 n，因此空间复杂度为 O(n)。