景安网站备案幕布,分销系统小程序开发,工业设计作品集案例,济南免费网站制作题解
给定 n 对括号#xff0c;要求编写一个函数生成所有合法的括号组合。合法的括号组合必须满足每一对括号中的左括号必须先于右括号#xff0c;并且括号数量必须平衡。
题目描述
输入#xff1a;
一个整数 n#xff0c;表示括号的对数#xff0c;满足 0 ≤ n ≤ 1…题解
给定 n 对括号要求编写一个函数生成所有合法的括号组合。合法的括号组合必须满足每一对括号中的左括号必须先于右括号并且括号数量必须平衡。
题目描述
输入
一个整数 n表示括号的对数满足 0 ≤ n ≤ 10 0 \leq n \leq 10 0≤n≤10。
输出
返回一个包含所有合法括号组合的字符串数组。
示例1
输入
1输出
[()]示例2
输入
2输出
[(()), ()()]题解思路
这个问题是一个典型的递归回溯问题。我们可以通过递归来生成所有可能的括号组合。具体步骤如下
用递归函数生成括号的组合。每次递归调用时有两个选择 如果左括号还没有用完就添加一个左括号 (。如果右括号的数量小于左括号的数量且右括号还没有用完就添加一个右括号 )。 当左右括号的数量都达到了 n 时表示一个合法的组合已经完成将其加入结果数组。
时间复杂度和空间复杂度
时间复杂度O( 2 n 2^n 2n)因为每一层递归有两种选择添加左括号或右括号。空间复杂度O( n n 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;
}
解析 DFS函数的递归逻辑 DFS(left, right, ret, str, n, returnSize)是递归的核心函数left 和 right 分别表示已使用的左括号和右括号数量。如果left和right都达到了n就将当前字符串str存放括号组合存入ret数组。如果left n我们可以继续添加左括号。如果right left我们可以继续添加右括号。 空间分配 结果数组ret被分配了2000个空间可以容纳所有合法组合理论上可能达到O(4^n)个组合但实际上不会达到这么多。每个合法的括号组合是一个长度为2n的字符串因此str的长度是2n。 返回值 ret返回存放合法括号组合的数组returnSize返回合法组合的数量。
总结
通过递归的方式我们能够高效地生成所有合法的括号组合。递归回溯方法简洁而直观适合解决此类组合生成的问题。
