Java中等题-括号天生（力扣）

数字 n 代表天生括号的对数，请你计划一个函数，用于可以或许天生所有可能的并且 有用的 括号组合。
示例 1：

1. <strong>输入：</strong>n = 3
2. <strong>输出：</strong>["((()))","(()())","(())()","()(())","()()()"]

复制代码

示例 2：

1. <strong>输入：</strong>n = 1
2. <strong>输出：</strong>["()"]

复制代码

这道题我没有思路，我直接看的力扣官方的解题思路
回溯法：

1. class Solution {
2.     public List<String> generateParenthesis(int n) {
3.         List<String> ans=new ArrayList<>();
4.         StringBuilder str=new StringBuilder();
5.         int start=0;
6.         int end=0;
7.         generateTree(ans,str,start,end,n);
8.         return ans;
9.     }
10.     public static void generateTree(List<String> ans,StringBuilder str,int start,int end,int n){
11.         if (str.length()==n*2) {
12.             ans.add(String.valueOf(str));
13.             return;
14.         }
15.         if(start<n){
16.             str.append('(');
17.             generateTree(ans,str,start+1,end,n);
18.             str.deleteCharAt(str.length()-1);
19.         }
20.         if(end<start){
21.             str.append(')');
22.             generateTree(ans,str,start,end+1,n);
23.             str.deleteCharAt(str.length()-1);
25.         }
26.     }
27. }

复制代码

让AI来为我们详细解释一下：

1. class Solution {  
2.     // 公开方法，用于生成所有可能的括号组合  
3.     public List<String> generateParenthesis(int n) {  
4.         List<String> ans = new ArrayList<>();
5.         StringBuilder str = new StringBuilder(); // 创建一个StringBuilder对象，用于构建当前的括号组合  
6.       
7.         // 通常我们会用两个计数器来跟踪左括号和右括号的数量   
8.         generateTree(ans, str, 0, 0, n); // 调用递归方法开始生成括号组合，start和end初始都为0  
9.         return ans; // 返回包含所有括号组合的列表  
10.     }  
11.   
12.     // 静态递归方法，用于生成括号组合  
13.     // ans: 存储所有有效组合的列表  
14.     // str: 当前正在构建的括号组合  
15.     // start: 表示已添加的左括号数量  
16.     // end: 表示已添加的右括号数量  
17.     // n: 需要生成的括号对数  
18.     public static void generateTree(List<String> ans, StringBuilder str, int start, int end, int n) {  
19.         if (str.length() == n * 2) { // 如果当前组合的长度等于2n，说明已经生成了一个完整的括号组合  
20.             ans.add(String.valueOf(str));  
21.             return;  
22.         }  
23.         if (start < n) { // 如果还可以添加左括号（即已添加的左括号数量小于n）  
24.             str.append('('); // 向当前组合中添加一个左括号  
25.             generateTree(ans, str, start + 1, end, n); // 递归调用，尝试添加下一个字符
26.             str.deleteCharAt(str.length() - 1); // 回溯，撤销上一步添加的左括号  
27.         }  
28.         if (end < start) { // 如果还可以添加右括号（即已添加的右括号数量小于已添加的左括号数量）  
29.             str.append(')'); // 向当前组合中添加一个右括号  
30.             generateTree(ans, str, start, end + 1, n); // 递归调用，尝试添加下一个字符
31.             str.deleteCharAt(str.length() - 1); // 回溯，撤销上一步添加的右括号  
32.         }  
33.     }  
34. }  
35.   

复制代码

第一个 if 循环（添加左括号）

当 open < max 时，算法会尝试添加一个左括号到当前的括号组合中（cur.append('(');）。然后，它递归地调用本身（backtrack(...)），在添加了左括号的基础上继续天生括号组合。递归调用返回后，算法须要撤销刚才添加的左括号，以便在当前的 open 计数下尝试添加右括号或其他可能的操纵。这就是 cur.deleteCharAt(cur.length() - 1); 在第一个 if 循环之后的作用。
第二个 if 循环（添加右括号）

当 close < open 时，算法会尝试添加一个右括号到当前的括号组合中（cur.append(')');）。与添加左括号的环境雷同，它也递归地调用本身，在添加了右括号的基础上继续天生括号组合。递归调用返回后，同样须要撤销刚才添加的右括号，以便在当前的状态下尝试其他可能的操纵（好比继续添加右括号，或者在添加更多左括号之后再次尝试添加右括号）。因此，cur.deleteCharAt(cur.length() - 1); 也被用在了第二个 if 循环之后。
总结

cur.deleteCharAt(cur.length() - 1); 的使用是回溯算法的一个典范特性。它允许算法在尝试了一条路径之后，可以或许撤销上一步的操纵，并回到之前的状态，以便尝试其他可能的路径。在天生括号组合的问题中，这确保了算法可以或许系统地探索所有可能的括号组合，而不会陷入无限循环或错过任何有用的组合。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。