# 0022. 括号生成 ## 题目地址(22. 括号生成) <https://leetcode-cn.com/problems/generate-parentheses> ## 题目描述 ``` <pre class="calibre18">``` 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 示例： 输入：n = 3 输出：[ "((()))", "(()())", "(())()", "()(())", "()()()" ] ``` ``` ## 前置知识 - DFS - 回溯法 ## 公司 - 阿里 - 百度 - 腾讯 - 字节 ## 思路 深度优先搜索(回溯思想)，从空字符串开始构造，做加法。 ## 关键点 - 当 l < r 时记得剪枝 ## 代码 - 语言支持：JS ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number} n * @return {string[]} * @param l 左括号已经用了几个 * @param r 右括号已经用了几个 * @param str 当前递归得到的拼接字符串结果 * @param res 结果集 */</span> <span class="hljs-keyword">const</span> generateParenthesis = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">n</span>) </span>{ <span class="hljs-keyword">const</span> res = []; <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">dfs</span>(<span class="hljs-params">l, r, str</span>) </span>{ <span class="hljs-keyword">if</span> (l == n && r == n) { <span class="hljs-keyword">return</span> res.push(str); } <span class="hljs-title">// l 小于 r 时不满足条件 剪枝</span> <span class="hljs-keyword">if</span> (l < r) { <span class="hljs-keyword">return</span>; } <span class="hljs-title">// l 小于 n 时可以插入左括号，最多可以插入 n 个</span> <span class="hljs-keyword">if</span> (l < n) { dfs(l + <span class="hljs-params">1</span>, r, str + <span class="hljs-string">"("</span>); } <span class="hljs-title">// r < l 时 可以插入右括号</span> <span class="hljs-keyword">if</span> (r < l) { dfs(l, r + <span class="hljs-params">1</span>, str + <span class="hljs-string">")"</span>); } } dfs(<span class="hljs-params">0</span>, <span class="hljs-params">0</span>, <span class="hljs-string">""</span>); <span class="hljs-keyword">return</span> res; }; ``` ``` **复杂度分析** - 时间复杂度：O(2^N) - 空间复杂度：O(2^N) 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。