刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

4.生成括号
Paul是一名数学专业的同学，在课余选修了C++编程课，现在他能够自己写程序判断判断一个给定的由'('和')'组成的字符串是否是正确匹配的。可是他不满足于此，想反其道而行之，设计一个程序，能够生成所有合法的括号组合，请你帮助他解决这个问题。
时间限制：1000
内存限制：65536
输入
输入只有一行N，代表生成括号的对数（1 ≤ N ≤ 10)。
输出
输出所有可能的并且有效的括号组合，按照字典序进行排列，每个组合占一行。
样例输入
3
样例输出
((()))
(()())
(())()
()(())
()()()

使用微信搜索喵呜刷题，轻松应对考试！

答案：

略

解析：

【喵呜刷题小喵解析】：本题要求生成所有合法的括号组合，按照字典序进行排列，每个组合占一行。我们可以使用递归的方式来解决这个问题。具体思路如下：1. 定义一个递归函数generate(n, open, cur, res)，其中n表示还需要生成的括号对数，open表示当前已经生成的左括号数量，cur表示当前已经生成的括号组合，res表示最终的结果。2. 如果open为0且n也为0，说明已经生成了n对括号，且没有多余的左括号，此时将cur加入到结果res中。3. 如果n大于0，说明还需要生成n对括号，此时可以选择生成一个左括号，即调用generate(n-1, open+1, cur+"(", res)。4. 如果open大于0，说明当前已经生成的括号组合中左括号数量大于右括号数量，此时可以选择生成一个右括号，即调用generate(n, open-1, cur+")", res)。5. 在主函数中，首先读入n，然后调用generate(n, 0, "", res)生成所有合法的括号组合，最后遍历res输出每个组合。时间复杂度为O(n*2^n)，空间复杂度为O(2^n)。
创作类型：
原创

本文链接：4.生成括号 Paul是一名数学专业的同学，在课余选修了C++编程课，现在他能够自己写程序判断判

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share