题解 | 括号生成

1、解题思路

1. 回溯法：使用回溯法递归生成所有可能的括号组合。在每一步递归中，可以选择添加开括号 ( 或闭括号 ) ，但必须满足以下条件： 开括号的数量不能超过 n。闭括号的数量不能超过开括号的数量。当开括号和闭括号的数量均等于 n 时，得到一个合法组合。时间复杂度：O(2^n)，空间复杂度：O(n)（递归栈的深度）。
2. 动态规划：可以基于动态规划的思想，利用小规模问题的解来构建大规模问题的解。这种方法的时间复杂度也是 O(2^n)，但空间复杂度略高。

2、代码实现

C++

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串vector
     */
    vector<string> generateParenthesis(int n) {
        // write code here
        vector<string> result;
        backtrack(result, "", 0, 0, n);
        return result;
    }

    void backtrack(vector<string>& result, string current, int open, int close,
                   int max) {
        if (current.length() == max * 2) {
            result.push_back(current);
            return ;
        }
        if (open < max) {
            backtrack(result, current + "(", open + 1, close, max);
        }
        if (close < open) {
            backtrack(result, current + ")", open, close + 1, max);
        }
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        ArrayList<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }

    private void backtrack(ArrayList<String> result, String current, int open, int close, int max) {
        if (current.length() == max * 2) {
            result.add(current);
            return;
        }
        if (open < max) {
            backtrack(result, current + "(", open + 1, close, max);
        }
        if (close < open) {
            backtrack(result, current + ")", open, close + 1, max);
        }
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return string字符串一维数组
#
class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        # write code here
        result = []
        self.backtrack(result, "", 0, 0, n)
        return result

    def backtrack(self, result, current, open, close, max):
        if len(current) == max * 2:
            result.append(current)
            return
        if open < max:
            self.backtrack(result, current + "(", open + 1, close, max)
        if close < open:
            self.backtrack(result, current + ")", open, close + 1, max)

3、复杂度分析

1. 递归条件： 开括号的数量不能超过 n，否则无法闭合。闭括号的数量不能超过开括号的数量，否则会出现不匹配的闭括号。
2. 终止条件： 当当前字符串的长度等于 n * 2 时，说明已经生成了一个合法的括号组合。
3. 效率： 时间复杂度：O(2^n)，因为每个位置最多有两种选择（开括号或闭括号）。空间复杂度：O(n)，用于存储递归栈和当前字符串。
4. 适用性： 回溯法是解决括号生成问题的经典方法，适用于小规模数据（n ≤ 10）。如果数据规模较大，应考虑其他优化方法或限制条件。