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

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);
    }
}