当前位置：首页 > ops >正文

2025年- H73-Lc181--22.括号生成(回溯,组合）--Java版

ops 2025/6/27 17:01:35

1.题目描述
在这里插入图片描述

2.思路
在这里插入图片描述

（1）终止条件：如果当前字符串长度为 2 * n，说明括号已经填满（n 个左括号和 n 个右括号），加入结果列表并返回。
（2）如果还没用完所有的左括号（open < n），就可以继续加左括号。递归调用：左括号数量加 1，继续构造。回溯关键步骤：撤销上一步加的括号，回到上一个状态，尝试其他组合。
（3）如果当前右括号数量比左括号少（close < open），则可以加一个右括号。
与左括号逻辑类似：加右括号 → 递归 → 撤销（回溯）。
（4）new stringbuffer()是可变字符串长度

3.代码实现

import java.util.ArrayList;
import java.util.List;public class H22 {public List<String> generateParenthesis(int n) {//保存括号字符串的结果List<String> result=new ArrayList<>();//可变字符串，存储回溯过程中的括号StringBuffer sb=new StringBuffer();//第1个0代表左括号的数量，第2个0代表右括号的数量，n代表括号对的数量backTracking(result,sb,0,0,n);return result;}public void backTracking(List<String> result,StringBuffer cur,int left,int right,int n){if(cur.length()==n*2){result.add(cur.toString());}//先拿左括号和要生成的括号对数进行比较，之后左括号填满之后，开始补齐右括号，如果右括号数量小于左括号数量，补齐右括号if(left<n)//如果左括号小于输入的括号对数{cur.append('(');backTracking(result,cur,left+1,right,n);cur.deleteCharAt(cur.length()-1);//cur.length()-1是整数，cur是可变字符串，所以要用到cur.deleteCharAt（index）}if(right<left){//右括号数量少（右括号小于左括号），开始补齐右括号cur.append(')');backTracking(result,cur,left,right+1,n);cur.deleteCharAt(cur.length()-1);}}public static void main(String[] args){H22 test=new H22();int n=3;List<String> ans=test.generateParenthesis(n);System.out.print(ans);}
}