LeetCode LCR 085. 括号生成

Categories:

题目描述
思路分析
1. 解法一：回溯（推荐）
相似题目

题目描述

✅ LCR 085. 括号生成

思路分析

解法一：回溯（推荐）

核心思路：

暴力枚举所有 2n 位的括号序列再过滤，复杂度过高。利用约束条件在生成过程中提前剪枝。

合法括号前缀的两个约束：1）已放左括号数 left ≤ n（不能超过总对数）；2）已放右括号数 right ≤ left（右括号不能多于左括号，保证任意前缀合法）。

回溯过程（DFS 搜索树）：每一步有两个选择：放 ( 或放 )。放 (：要求 left < n；放 )：要求 right < left；当 len(cur) == 2n 时，收集结果。

满足上述两个约束的序列，任意前缀中左括号数 ≥ 右括号数，且最终左右各 n 个，必然合法。结果数量为第 n 个卡特兰数 $C_n = \frac{1}{n+1}\binom{2n}{n}$。

复杂度分析：

时间复杂度：O(Cₙ × n)，其中 Cₙ 为第 n 个卡特兰数，n 为括号对数

空间复杂度：O(n)，其中 n 为括号对数，即递归深度（不含结果集）

class Solution {

  public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    backtrack(res, new StringBuilder(), 0, 0, n);
    return res;
  }

  private void backtrack(List<String> res, StringBuilder cur, int left, int right, int n) {
    // 当前序列长度达到 2n，收集结果
    if (cur.length() == 2 * n) {
      res.add(cur.toString());
      return;
    }
    // 左括号数量未达上限，可以放左括号
    if (left < n) {
      cur.append('(');
      backtrack(res, cur, left + 1, right, n);
      cur.deleteCharAt(cur.length() - 1);
    }
    // 右括号数量小于左括号数量，可以放右括号
    if (right < left) {
      cur.append(')');
      backtrack(res, cur, left, right + 1, n);
      cur.deleteCharAt(cur.length() - 1);
    }
  }
}

func generateParenthesis(n int) []string {
	var res []string
	var backtrack func(string, int, int)

	backtrack = func(cur string, left, right int) {
		// 当前序列长度达到 2n，收集结果
		if len(cur) == 2*n {
			res = append(res, cur)
			return
		}
		// 左括号数量未达上限，可以放左括号
		if left < n {
			backtrack(cur+"(", left+1, right)
		}
		// 右括号数量小于左括号数量，可以放右括号
		if right < left {
			backtrack(cur+")", left, right+1)
		}
	}

	backtrack("", 0, 0)
	return res
}

相似题目

题目	难度	考察点
20. 有效的括号	简单	栈
32. 最长有效括号	困难	动态规划、栈
301. 删除无效的括号	困难	回溯
1249. 移除无效的括号	中等	栈 + 贪心
678. 有效的括号字符串	中等	贪心
856. 括号的分数	中等	栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/49601822