【刷题记录】22. 括号生成

2022 年 7 月 26 日
本文字数：745 字
阅读完需：约 2 分钟

一、题目描述

来源：力扣（LeetCode）数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3输出：["((()))","(()())","(())()","()(())","()()()"]

复制代码

示例 2：

输入：n = 1输出：["()"]

复制代码

提示：

1 <= n <= 8

二丶思路分析

回溯法

对于n对括号，会有 n个( 和 n个) 一共 2n 个字符

我们使用 DFS 来递归生产所有的序列情况，为了减少递归的次数，每次递归时候

左括号数量不大于 n，我们可以放一个左括号。
如果右括号数量小于左括号的数量，我们就放一个右括号。来保证我们的括号是成对而且有效的。

三、代码实现

class Solution {    public List<String> generateParenthesis(int n) {        List<String> res = new ArrayList<String>();        dfs(res, new StringBuilder(), 0, 0, n);        return res;    }
    public void dfs(List<String> ans, StringBuilder cur, int l, int r, int len) {        if (cur.length() == len * 2) {            ans.add(cur.toString());            return;        }        if (l < len) {            cur.append('(');            dfs(ans, cur, l + 1, r, len);            cur.deleteCharAt(cur.length() - 1);        }        if (r < l) {            cur.append(')');            dfs(ans, cur, l, r + 1, len);            cur.deleteCharAt(cur.length() - 1);        }    }}

复制代码

复杂度分析

时间复杂度：典型的卡特兰数问题，复杂度为 $O (C_{2 n}^{n})$ n个左括号的个数。
空间复杂度： $O (n)$

运行结果

总结

这道题就是遍历所有 n 对括号组合生成的字符串，然后做有效括号的验证。

但是这些会产生比较多不符合的。所以我们可以根据规律，进一步的缩小范围，让它只递归产生我们需要的结果。

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/a1f9ec116cbc849fe3d80527c】。

WangNing

关注

还未添加个人签名 2020.10.13 加入

一个只想提(快)升(乐)自(摸)我(鱼)的混子选手～

发布

暂无评论

创作场景

【刷题记录】22. 括号生成

一、题目描述

二丶思路分析

三、代码实现

复杂度分析

运行结果

总结

WangNing

评论