- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
回溯法
题目要求我们生成所有可能的有效的括号组合，数字 n 代表生成括号的对数。
使用回溯法进行解题，从空字符串开始构造，做加法。
- 当 l < r 时(构造用的左括号 < 构造用的右括号)，不满足条件，直接剪枝。
- 当 l < n 时，可以一直插入左括号，最多插入 n 个。
- 当 r < l (构造用的右括号 < 构造用的左括号)时，可以插入右括号。
constgenerateParenthesis=function(n){constres=[]functiongenerate(l,r,str){// 递归终止条件if(l===n&&r===n){returnres.push(str)}if(l<r){return}if(l<n){generate(l+1,r,str+'(')}if(r<l){generate(l,r+1,str+')')}}generate(0,0,'')returnres}
- 时间复杂度：O(2^n)
- 空间复杂度：O(2^n)