括号生成

本题要求生成所有可能的且有效的括号组合。对于每个括号组合，都必须满足：

• 左括号 "(" 的数量等于右括号 ")" 的数量；
• 任意位置上，左括号的数量不能少于右括号的数量。

题解思路

算法思路

使用 回溯法 是解决本题的经典方法。回溯法的核心在于递归地构建字符串，同时根据当前已添加的左右括号的数量判断是否可以继续添加：

1. 递归终止条件：
   当左括号和右括号都达到 n 个时，当前构造的字符串就是一个有效的括号组合，将其加入答案列表。

2. 递归决策：

   • 如果左括号的数量小于 n，则可以继续添加左括号 "("。
   • 如果右括号的数量小于左括号的数量，则可以添加右括号 ")"，以保持当前字符串的合法性。

通过这种方式，可以保证构造出的所有字符串都是有效的括号组合。

复杂度分析

• 时间复杂度：
  有效括号组合的总数为卡塔兰数 $C_n = \frac{1}{n+1}\binom{2n}{n}$，因此算法的时间复杂度为 $O(C_n \times n)$，其中 $n$ 是构造每个组合所需的时间（用于复制字符串或构造新字符串）。

• 空间复杂度：
  递归调用的深度为 $2n$，另外需要存储所有 $C_n$ 个结果，因此空间复杂度为 $O(C_n \times n)$。

Python代码

def generate_parentheses(n: int):
    # 结果列表，用于存放所有有效的括号组合
    res = []
    
    def backtrack(s: str, left: int, right: int):
        # 如果左右括号都达到 n，则找到一个有效组合
        if left == n and right == n:
            res.append(s)
            return
        # 如果左括号数量小于 n，则可以添加左括号
        if left < n:
            backtrack(s + "(", left + 1, right)
        # 如果右括号数量小于左括号，则可以添加右括号
        if right < left:
            backtrack(s + ")", left, right + 1)
    
    # 从空字符串开始，左括号和右括号均为0
    backtrack("", 0, 0)
    return res

if __name__ == "__main__":
    n = int(input().strip())
    results = generate_parentheses(n)
    # 按要求每行输出一个结果
    for combination in results:
        print(combination)

JAVA代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    // 主函数
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<String> result = generateParenthesis(n);
        // 每行输出一个有效组合
        for (String s : result) {
            System.out.println(s);
        }
        sc.close();
    }
    
    // 生成所有有效括号组合的函数
    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(res, "", 0, 0, n);
        return res;
    }
    
    // 回溯函数
    private static void backtrack(List<String> res, String s, int left, int right, int n) {
        // 当左右括号都达到 n 时，将当前组合加入结果列表
        if (left == n && right == n) {
            res.add(s);
            return;
        }
        // 如果左括号数量小于 n，则添加左括号
        if (left < n) {
            backtrack(res, s + "(", left + 1, right, n);
        }
        // 如果右括号数量小于左括号数量，则添加右括号
        if (right < left) {
            backtrack(res, s + ")", left, right + 1, n);
        }
    }
}

C++代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 回溯函数，用于生成所有有效括号组合
void backtrack(vector<string>& res, string s, int left, int right, int n) {
    // 如果左右括号数量均达到 n，说明得到一个有效组合
    if (left == n && right == n) {
        res.push_back(s);
        return;
    }
    // 如果左括号数量小于 n，则可以添加左括号
    if (left < n)
        backtrack(res, s + "(", left + 1, right, n);
    // 如果右括号数量小于左括号，则可以添加右括号
    if (right < left)
        backtrack(res, s + ")", left, right + 1, n);
}

int main() {
    int n;
    cin >> n;
    vector<string> res;
    // 从空字符串开始构造括号组合
    backtrack(res, "", 0, 0, n);
    // 每行输出一个有效括号组合
    for (const auto &s : res) {
        cout << s << endl;
    }
    return 0;
}

Leetcode 59.括号生成-原题链接

题目内容

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

输入描述

一个整数$n$。

输出描述

输出若干行，每行一个字符串，代表一个有效的括号组合。

样例1

输入

3

输出

((()))
(()())
(())()
()(())
()()()

样例2

输入

1

输出

()

提示：

• $1 <= n <= 8$