【回溯】LCR 085. 括号生成

本文主要是介绍【回溯】LCR 085. 括号生成，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LCR 085. 括号生成

解题思路

首先，我们定义一个公共方法 generateParenthesis，该方法接受一个整数 n，表示要生成括号的对数。如果 n 为零，直接返回一个空列表。
然后，在 generateParenthesis 方法中，我们初始化一个空列表 res 和一个空的字符串构建器 track。接着，我们调用 backtrack 方法进行回溯，并将 track 和 res 作为参数传递给它。
在 backtrack 方法中，我们设置筛选条件，即右括号数量不能超过左括号数量。如果出现右括号数量超过左括号数量的情况，直接返回。同时，如果左括号或右括号的数量小于零，也直接返回。
接着，当左右括号数量都为零时，将当前 track 所代表的括号组合加入到结果列表 res 中，并返回。
然后，我们进行选择。首先，在 track 中添加左括号，并递归调用 backtrack 方法，同时更新左括号的数量。当递归返回后，撤销选择，即从 track 中删除最后一个字符。
接着，我们再在 track 中添加右括号，并递归调用 backtrack 方法，同时更新右括号的数量。同样地，当递归返回后，撤销选择，即从 track 中删除最后一个字符。
最终，当所有的递归调用都完成后，res 中存储的就是所有有效的括号组合。

class Solution {public List<String> generateParenthesis(int n) {if(n == 0){return new ArrayList<>();}List<String> res = new ArrayList<>();StringBuilder track = new StringBuilder();backtrack(n,n,track,res);return res;}void backtrack(int left,int right,StringBuilder track,List<String> res){// 筛选条件： 左右括号相等  任意字串内 左括号数量需要大于等于右括号数量if(right < left){return;}if (left < 0 || right < 0) return;// 当所有的括号恰好用完的时候  得到一个合法的括号组合if(left == 0 && right == 0){res.add(track.toString());return;}// 进行选择track.append('(');backtrack(left - 1,right,track,res);track.deleteCharAt(track.length() - 1);// 撤销选择 track.append(')');backtrack(left,right - 1,track,res);track.deleteCharAt(track.length() - 1);}
}