每日算法 — 使用java实现括号生成：回溯搜索与卡特兰数计数

问题描述

括号生成是一道经典的回溯算法题目。给定 n 对括号，编写一个函数来生成所有由 n 对括号组成的合法组合。合法括号序列要求每个左括号都有对应的右括号，且括号正确嵌套。

示例（n = 3）：

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

算法思路分析

方法一：回溯法（深度优先搜索）

在生成括号的过程中，维护两个计数器：left（已用左括号数）和 right（已用右括号数）。

• 只要 left < n，就可以添加左括号
• 只要 right < left，就可以添加右括号（保证合法性）
• 当 left == right == n 时，得到一个合法序列

方法二：卡特兰数公式

合法括号序列的数量等于第 n 个卡特兰数：

C(n) = (2n)! / ((n+1)! * n!)

卡特兰数在组合数学中广泛出现，包括二叉树形态数、出栈序列数等。

Java 完整实现

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

public class GenerateParentheses {

    /**
     * 方法一：回溯法生成所有合法括号序列
     * 时间复杂度：O(4^n / √n)，空间复杂度：O(n)
     */
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        StringBuilder current = new StringBuilder();
        backtrack(result, current, 0, 0, n);
        return result;
    }

    /**
     * 回溯核心逻辑
     * @param result  结果集合
     * @param current 当前构建的字符串
     * @param left    已使用的左括号数
     * @param right   已使用的右括号数
     * @param n       括号对数
     */
    private void backtrack(List<String> result, StringBuilder current,
                           int left, int right, int n) {
        // 终止条件：所有括号都已用完
        if (left == n && right == n) {
            result.add(current.toString());
            return;
        }

        // 选择1：添加左括号（只要还有剩余的左括号）
        if (left < n) {
            current.append('(');
            backtrack(result, current, left + 1, right, n);
            current.deleteCharAt(current.length() - 1); // 回溯
        }

        // 选择2：添加右括号（必须保证右括号少于左括号）
        if (right < left) {
            current.append(')');
            backtrack(result, current, left, right + 1, n);
            current.deleteCharAt(current.length() - 1); // 回溯
        }
    }

    /**
     * 方法二：递归构造（按括号嵌套层数分类）
     * 时间复杂度：O(4^n / √n)
     */
    public List<String> generateParenthesisDivide(int n) {
        List<String> result = new ArrayList<>();
        if (n == 0) {
            result.add("");
            return result;
        }

        // 外层括号内包含 p 对括号，外层右侧包含 (n-1-p) 对
        for (int p = 0; p < n; p++) {
            List<String> leftList = generateParenthesisDivide(p);
            List<String> rightList = generateParenthesisDivide(n - 1 - p);
            for (String left : leftList) {
                for (String right : rightList) {
                    result.add("(" + left + ")" + right);
                }
            }
        }
        return result;
    }

    /**
     * 方法三：动态规划
     * dp[i] 存储 i 对括号的所有合法序列
     */
    public List<String> generateParenthesisDP(int n) {
        if (n == 0) {
            List<String> base = new ArrayList<>();
            base.add("");
            return base;
        }

        @SuppressWarnings("unchecked")
        List<String>[] dp = new ArrayList[n + 1];
        dp[0] = new ArrayList<>();
        dp[0].add("");

        for (int i = 1; i <= n; i++) {
            dp[i] = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                for (String left : dp[j]) {
                    for (String right : dp[i - 1 - j]) {
                        dp[i].add("(" + left + ")" + right);
                    }
                }
            }
        }
        return dp[n];
    }

    /**
     * 计算合法括号序列的数量（卡特兰数）
     * 时间复杂度：O(n)，空间复杂度：O(1)
     */
    public long catalanNumber(int n) {
        long result = 1;
        // 利用递推公式：C(n) = C(n-1) * 2*(2n-1) / (n+1)
        for (int i = 0; i < n; i++) {
            result = result * 2 * (2 * i + 1) / (i + 2);
        }
        return result;
    }

    /**
     * 大数版本的卡特兰数（使用 long，可计算到 n=33）
     */
    public long catalanDirect(int n) {
        // C(2n, n) / (n + 1)
        long combination = 1;
        for (int i = 0; i < n; i++) {
            combination = combination * (2L * n - i) / (i + 1);
        }
        return combination / (n + 1);
    }

    /**
     * 验证括号序列是否合法
     */
    public boolean isValid(String s) {
        int balance = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                balance++;
            } else {
                balance--;
            }
            // 中间过程不能出现负值
            if (balance < 0) return false;
        }
        return balance == 0;
    }

    public static void main(String[] args) {
        GenerateParentheses solution = new GenerateParentheses();
        int n = 3;

        System.out.println("=== 括号生成问题 (n=" + n + ") ===");

        List<String> result1 = solution.generateParenthesis(n);
        System.out.println("回溯法结果 (" + result1.size() + " 个):");
        for (String s : result1) {
            System.out.println("  " + s + " -> 合法? " + solution.isValid(s));
        }

        List<String> result2 = solution.generateParenthesisDivide(n);
        System.out.println("\n分治法结果 (" + result2.size() + " 个):");
        for (String s : result2) {
            System.out.println("  " + s);
        }

        List<String> result3 = solution.generateParenthesisDP(n);
        System.out.println("\n动态规划结果 (" + result3.size() + " 个):");
        for (String s : result3) {
            System.out.println("  " + s);
        }

        System.out.println("\n卡特兰数 C(" + n + ") = " + solution.catalanNumber(n));
        System.out.println("直接公式 C(" + n + ") = " + solution.catalanDirect(n));

        // 测试更大的 n
        int bigN = 10;
        System.out.println("\n卡特兰数 C(" + bigN + ") = " + solution.catalanNumber(bigN));
    }
}

复杂度分析

扩展思考

1. 限制嵌套深度：生成的序列中括号最大嵌套层数不超过 k。
2. 多种括号：同时处理 ()、[]、{} 的合法组合。
3. 最长合法子串：给定一个括号字符串，找出最长的合法连续子串。

总结

括号生成问题通过简单的约束条件（right < left）展示了回溯算法的精髓：在递归的每一步做出选择，并在不满足条件时及时剪枝。同时，它与卡特兰数的深刻联系揭示了许多组合问题的统一结构。掌握这一经典模型，对于理解递归树、剪枝策略和组合计数都有重要意义。