欢迎来到李耶的频道【LeetCode面试题】。括号生成22.括号生成题目数字n代表生成括号的对数请你设计一个函数生成所有可能的并且有效的括号组合。输入n 3 输出[((())),(()()),(())(),()(()),()()()]输入n 1 输出[()]提示1 n 8解法一回溯法DFS推荐思路使用深度优先搜索维护两个计数器left和right分别表示已使用的左括号和右括号数量。在每一步可以选择添加左括号或右括号但必须满足左括号数量不能超过n右括号数量不能超过左括号数量保证有效性当左右括号都用完时得到一个有效组合functiongenerateParenthesis(n){constresult[];functionbacktrack(left,right,path){// 左右括号都用完了得到一个有效组合if(leftnrightn){result.push(path);return;}// 可以加左括号if(leftn){backtrack(left1,right,path();}// 可以加右括号右括号数量 左括号数量if(rightleft){backtrack(left,right1,path));}}backtrack(0,0,);returnresult;}时间复杂度 / 空间复杂度O(4^n / √n) / O(n)n 为括号对数优势经典回溯模板剪枝条件直观面试中最推荐的写法解法二动态规划思路dp[n]表示n对括号的所有有效组合。对于dp[n]可以将其拆分为( dp[i] ) dp[n - 1 - i]其中i表示内层括号的对数。functiongenerateParenthesis(n){if(n0)return[];constdpnewArray(n1).fill().map(()[]);dp[0][];for(leti1;in;i){for(letj0;ji;j){for(constinsideofdp[j]){for(constoutsideofdp[i-1-j]){dp[i].push((inside)outside);}}}}returndp[n];}时间复杂度 / 空间复杂度O(4^n / √n) / O(4^n / √n)优势体现最优子结构思想将大问题拆分为小问题劣势理解难度稍高空间占用较大解法对比解法时间 / 空间复杂度优势推荐指数回溯法DFSO(4^n / √n) / O(n)经典模板剪枝清晰⭐⭐⭐⭐⭐动态规划O(4^n / √n) / O(4^n / √n)体现DP思想解耦清晰⭐⭐⭐⭐扩展题有效的括号给定一个只包含括号的字符串判断是否有效。最长有效括号给定一个只包含(和)的字符串找出最长有效括号子串的长度。删除无效的括号给定一个由括号组成的字符串删除最少数量的括号使得结果字符串是有效的括号字符串。“工欲善其事必先利其器。” —— 《论语·卫灵公》关注李耶每天一道面试题一起卷起来
