Medium

题目描述

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= n <= 8

解题思路

这道题要求生成所有有效的括号组合，是典型的回溯问题。

思路分析：

有效括号的规则是：

  1. 左括号数量等于右括号数量
  2. 在任意前缀中，左括号数量始终大于等于右括号数量

我们可以用回溯法来生成所有可能的组合：

  • 当前字符串长度达到 2n 时，说明找到一个有效组合
  • 如果左括号数量小于 n，可以添加左括号
  • 如果右括号数量小于左括号数量，可以添加右括号

常见解法：

  1. 回溯法（推荐）： 通过递归生成所有可能的组合，时间复杂度最优
  2. 动态规划： 利用 dp[i] 表示 i 对括号的所有组合，通过组合小问题的解构建大问题的解
  3. 暴力枚举： 生成所有可能的括号序列再筛选有效的，效率较低

回溯法是最直观且高效的解法，代码简洁易懂。

代码实现

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        backtrack(result, "", 0, 0, n);
        return result;
    }
    
private:
    void backtrack(vector<string>& result, string current, int open, int close, int n) {
        if (current.length() == 2 * n) {
            result.push_back(current);
            return;
        }
        
        if (open < n) {
            backtrack(result, current + "(", open + 1, close, n);
        }
        if (close < open) {
            backtrack(result, current + ")", open, close + 1, n);
        }
    }
};

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        
        def backtrack(current, open_count, close_count):
            if len(current) == 2 * n:
                result.append(current)
                return
            
            if open_count < n:
                backtrack(current + "(", open_count + 1, close_count)
            if close_count < open_count:
                backtrack(current + ")", open_count, close_count + 1)
        
        backtrack("", 0, 0)
        return result

public class Solution {
    public IList<string> GenerateParenthesis(int n) {
        var result = new List<string>();
        Backtrack(result, "", 0, 0, n);
        return result;
    }
    
    private void Backtrack(IList<string> result, string current, int open, int close, int n) {
        if (current.Length == 2 * n) {
            result.Add(current);
            return;
        }
        
        if (open < n) {
            Backtrack(result, current + "(", open + 1, close, n);
        }
        if (close < open) {
            Backtrack(result, current + ")", open, close + 1, n);
        }
    }
}

var generateParenthesis = function(n) {
    const result = [];
    
    function backtrack(current, open, close) {
        if (current.length === 2 * n) {
            result.push(current);
            return;
        }
        
        if (open < n) {
            backtrack(current + '(', open + 1, close);
        }
        
        if (close < open) {
            backtrack(current + ')', open, close + 1);
        }
    }
    
    backtrack('', 0, 0);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型回溯法
时间复杂度O(4^n / √n)
空间复杂度O(4^n / √n)

说明：

  • 时间复杂度：第 n 个卡塔兰数为 O(4^n / √n)，这是有效括号序列的数量
  • 空间复杂度：除了存储结果外，递归栈的深度最大为 2n

相关题目