leetcode-22.括号生成

暴力

感谢分享这个思路和算法。生成括号的问题可以通过生成所有可能的括号序列并验证其有效性来解决。以下是对该思路的详细解释和实现：

思路

1. 生成所有可能的序列：

   • 使用递归生成所有长度为 2n 的括号序列。在每个位置可以选择放置 '(' 或 ')'。

2. 验证序列的有效性：

   • 使用一个变量 balance 来记录左括号 '(' 的数量减去右括号 ')' 的数量。
   • 在遍历序列的过程中，如果 balance 小于零，说明在某个位置右括号多于左括号，该序列无效。
   • 如果遍历结束时 balance 不为零，说明左括号和右括号数量不匹配，该序列无效。
   • 只有当 balance 始终大于等于零并在结束时等于零，序列才是有效的。

实现

以下是这个思路的 Java 实现：

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

public class GenerateParentheses {

    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generateAll(new char[2 * n], 0, result);
        return result;
    }

    private void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (isValid(current)) {
                result.add(new String(current));
            }
        } else {
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }
    }

    private boolean isValid(char[] current) {
        int balance = 0;
        for (char c : current) {
            if (c == '(') {
                balance++;
            } else {
                balance--;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }

    public static void main(String[] args) {
        GenerateParentheses gp = new GenerateParentheses();
        List<String> result = gp.generateParenthesis(3);
        System.out.println(result);
    }
}

关键点

• 递归生成：通过递归生成所有可能的括号组合，每次递归选择放置 '(' 或 ')'。
• 有效性检查：使用 isValid 方法检查生成的序列是否有效，确保左括号数量始终不少于右括号，并且最终数量相等。
• 时间复杂度：该方法生成所有可能的序列并检查其有效性，时间复杂度相对较高，为 O(2^(2n) * n)，因为每个序列的生成和验证都需要线性时间。

这种方法简单直接，但在生成所有可能的序列时效率较低。对于大规模输入，可能需要优化或使用其他方法（如回溯法）来提高效率。

回溯

使用回溯法来生成有效的括号组合是一种更高效的方法。通过在生成序列的过程中只添加可能导致有效序列的括号，可以避免生成所有可能的组合，从而提高效率。

思路和算法

1. 递归构建序列：

   • 使用递归函数来构建括号序列。
   • 维护两个计数器：一个记录已放置的左括号 '(' 的数量，另一个记录已放置的右括号 ')' 的数量。

2. 添加左括号：

   • 只要左括号的数量小于 n，就可以继续添加左括号。

3. 添加右括号：

   • 只有在右括号的数量小于左括号的数量时，才可以添加右括号。这确保了在任何时候都不会出现未匹配的右括号。

4. 终止条件：

   • 当左右括号的数量都达到 n 时，生成一个完整且有效的括号序列。

实现

以下是使用回溯法的 Python 实现：

def generateParenthesis(n):
    def backtrack(S, left, right):
        if len(S) == 2 * n:
            result.append("".join(S))
            return
        if left < n:
            S.append('(')
            backtrack(S, left + 1, right)
            S.pop()
        if right < left:
            S.append(')')
            backtrack(S, left, right + 1)
            S.pop()

    result = []
    backtrack([], 0, 0)
    return result

# Example usage:
print(generateParenthesis(3))

关键点

• 递归与回溯：通过递归构建序列，并在每一步选择添加 '(' 或 ')'。使用回溯在递归返回时撤销选择（通过 pop 操作），以便探索其他选择。
• 剪枝条件：通过限制左括号和右括号的添加，避免生成无效的序列。
• 效率：相比于生成所有可能的序列并验证其有效性，回溯法通过剪枝大大减少了需要生成和检查的序列数量，从而提高了效率。

这种方法在生成括号问题中是非常有效的，因为它利用了括号匹配的性质，只在可能导致有效序列的情况下进行递归。