每日一题——括号生成

题解

给定 n 对括号，要求编写一个函数生成所有合法的括号组合。合法的括号组合必须满足每一对括号中的左括号必须先于右括号，并且括号数量必须平衡。

题目描述

输入：

• 一个整数 n，表示括号的对数，满足 $0\le n\le 10$。

输出：

• 返回一个包含所有合法括号组合的字符串数组。

示例1

输入：

1

输出：

["()"]

示例2

输入：

2

输出：

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

题解思路

这个问题是一个典型的递归回溯问题。我们可以通过递归来生成所有可能的括号组合。具体步骤如下：

1. 用递归函数生成括号的组合。
2. 每次递归调用时，有两个选择：
   • 如果左括号还没有用完，就添加一个左括号 '('。
   • 如果右括号的数量小于左括号的数量，且右括号还没有用完，就添加一个右括号 ')'。
3. 当左右括号的数量都达到了 n 时，表示一个合法的组合已经完成，将其加入结果数组。

时间复杂度和空间复杂度

• 时间复杂度：O($2^n$)，因为每一层递归有两种选择（添加左括号或右括号）。
• 空间复杂度：O($n$)，由于递归调用栈的深度是 n，每次递归都在 2n 长度的字符串上操作。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>/*** 深度优先搜索（DFS）函数，用于生成所有有效的括号组合* * @param left 左括号的数量* @param right 右括号的数量* @param ret 存储所有生成的括号组合的数组* @param path 当前路径，即当前生成的括号组合* @param n 括号对数* @param returnSize 当前已生成的括号组合数量*/
void DFS(int left, int right, char **ret, char* path, int n, int *returnSize) {// 如果左括号和右括号的数量都等于 n，说明生成了一个有效的括号组合if (left == n && right == n) {// 为当前括号组合分配内存，长度为 2n + 1（包括字符串终止符）ret[*returnSize] = malloc(sizeof(char) * (2 * n + 1));if (ret[*returnSize] == NULL) {printf("Memory allocation failed\n");exit(1);}// 将当前路径复制到结果数组中for (int i = 0; i < 2 * n; i++) {ret[*returnSize][i] = path[i];}ret[*returnSize][2 * n] = '\0'; // 添加字符串终止符// 增加已生成的括号组合数量(*returnSize)++;return;}// 如果左括号的数量小于 n，可以添加一个左括号if (left < n) {path[left + right] = '('; // 在当前路径中添加左括号DFS(left + 1, right, ret, path, n, returnSize); // 递归调用，继续生成}// 如果右括号的数量小于左括号的数量且小于 n，可以添加一个右括号if (right < left && right < n) {path[left + right] = ')'; // 在当前路径中添加右括号DFS(left, right + 1, ret, path, n, returnSize); // 递归调用，继续生成}
}/*** 主函数，生成所有有效的括号组合* * @param n 括号对数* @param returnSize 返回的括号组合数量* @return 存储所有有效括号组合的数组*/
char** generateParenthesis(int n, int *returnSize) {// 预分配足够大的空间存储结果，这里假设最多有 2000 种组合char** ret = (char**)malloc(sizeof(char*) * 2000);if (ret == NULL) {printf("Memory allocation failed\n");exit(1);}*returnSize = 0; // 初始化返回的括号组合数量为 0// 为当前路径分配内存，长度为 2n + 1（包括字符串终止符）char* path = (char*)malloc(sizeof(char) * (2 * n + 1));if (path == NULL) {printf("Memory allocation failed\n");exit(1);}// 调用 DFS 函数生成所有有效的括号组合DFS(0, 0, ret, path, n, returnSize);// 释放当前路径的内存free(path);return ret;
}

解析

1. DFS函数的递归逻辑：

   • DFS(left, right, ret, str, n, returnSize)是递归的核心函数，left 和 right 分别表示已使用的左括号和右括号数量。
   • 如果left和right都达到了n，就将当前字符串str（存放括号组合）存入ret数组。
   • 如果left < n，我们可以继续添加左括号。
   • 如果right < left，我们可以继续添加右括号。

2. 空间分配：

   • 结果数组ret被分配了2000个空间，可以容纳所有合法组合（理论上可能达到O(4^n)个组合，但实际上不会达到这么多）。
   • 每个合法的括号组合是一个长度为2n的字符串，因此str的长度是2n。

3. 返回值：

   • ret返回存放合法括号组合的数组，returnSize返回合法组合的数量。

总结

通过递归的方式，我们能够高效地生成所有合法的括号组合。递归回溯方法简洁而直观，适合解决此类组合生成的问题。