Java教程

力扣22. 括号生成(JAVA)回溯法

本文主要是介绍力扣22. 括号生成(JAVA)回溯法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1、合法括号生成
力扣题解

22. 括号生成

难度中等2268

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:

输入:n = 1
输出:["()"]
解析

有关括号问题,你只要记住两个个性质,思路就很容易想出来:

1、一个「合法」括号组合的左括号数量一定等于右括号数量,这个显而易见

2、对于一个「合法」的括号字符串组合p,必然对于任何0 <= i < len(p)都有:子串p[0..i]中左括号的数量都大于或等于右括号的数量

可以改写成如下问题:

  • 现在有**2n个位置,每个位置可以放置字符(或者)****,组成的所有括号组合中,有多少个是合法的**?

对于2n个位置,必然有n个左括号,n个右括号,所以我们不是简单的记录穷举位置i,**而是left记录还可以使用多少个左括号,用right**记录还可以使用多少个右括号,这样就可以通过刚才总结的合法括号规律进行筛选了:

代码
class Solution {
    List<String> res=new ArrayList<>();
    StringBuilder track = new StringBuilder();
    String str[];
    public List<String> generateParenthesis(int n) {
        str = new String[]{"(", ")"};
        backtrack(n,n,track);
        return res;
    }
    //可用的左括号数量为 left 个,可用的右括号数量为 rgiht 个
    public void backtrack(int left,int right,StringBuilder track){
        // 若左括号剩下的多,说明不合法
        if(left>right) return;
        // 数量小于 0 肯定是不合法的
        if(left<0 || right<0) return;
         // 当所有括号都恰好用完时,得到一个合法的括号组合
        if(left==0 && right==0){
            res.add(new String(track));
        }
        // 尝试放一个左括号
        track.append(str[0]);
        backtrack(left-1,right,track);
        track.deleteCharAt(track.length()-1); 

        // 尝试放一个右括号
        track.append(str[1]);
        backtrack(left,right-1,track);
        track.deleteCharAt(track.length()-1);
    }
}
这篇关于力扣22. 括号生成(JAVA)回溯法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!