# 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。