數(shù)字?n?代表生成括號的對數(shù)，請你設(shè)計一個函數(shù)，用于能夠生成所有可能的并且?有效的?括號組合。

示例 1：

輸入：n = 3
輸出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

輸入：n = 1
輸出：["()"]

這道題我沒有思路，我直接看的力扣官方的解題思路

回溯法：

class Solution {public List<String> generateParenthesis(int n) {List<String> ans=new ArrayList<>();StringBuilder str=new StringBuilder();int start=0;int end=0;generateTree(ans,str,start,end,n);return ans;}public static void generateTree(List<String> ans,StringBuilder str,int start,int end,int n){if (str.length()==n*2) {ans.add(String.valueOf(str));return;}if(start<n){str.append('(');generateTree(ans,str,start+1,end,n);str.deleteCharAt(str.length()-1);}if(end<start){str.append(')');generateTree(ans,str,start,end+1,n);str.deleteCharAt(str.length()-1);}}
}

讓AI來為我們詳細解釋一下：

class Solution {  // 公開方法，用于生成所有可能的括號組合  public List<String> generateParenthesis(int n) {  List<String> ans = new ArrayList<>(); StringBuilder str = new StringBuilder(); // 創(chuàng)建一個StringBuilder對象，用于構(gòu)建當前的括號組合  // 通常我們會用兩個計數(shù)器來跟蹤左括號和右括號的數(shù)量   generateTree(ans, str, 0, 0, n); // 調(diào)用遞歸方法開始生成括號組合，start和end初始都為0  return ans; // 返回包含所有括號組合的列表  }  // 靜態(tài)遞歸方法，用于生成括號組合  // ans: 存儲所有有效組合的列表  // str: 當前正在構(gòu)建的括號組合  // start: 表示已添加的左括號數(shù)量  // end: 表示已添加的右括號數(shù)量  // n: 需要生成的括號對數(shù)  public static void generateTree(List<String> ans, StringBuilder str, int start, int end, int n) {  if (str.length() == n * 2) { // 如果當前組合的長度等于2n，說明已經(jīng)生成了一個完整的括號組合  ans.add(String.valueOf(str));  return;  }  if (start < n) { // 如果還可以添加左括號（即已添加的左括號數(shù)量小于n）  str.append('('); // 向當前組合中添加一個左括號  generateTree(ans, str, start + 1, end, n); // 遞歸調(diào)用，嘗試添加下一個字符str.deleteCharAt(str.length() - 1); // 回溯，撤銷上一步添加的左括號  }  if (end < start) { // 如果還可以添加右括號（即已添加的右括號數(shù)量小于已添加的左括號數(shù)量）  str.append(')'); // 向當前組合中添加一個右括號  generateTree(ans, str, start, end + 1, n); // 遞歸調(diào)用，嘗試添加下一個字符str.deleteCharAt(str.length() - 1); // 回溯，撤銷上一步添加的右括號  }  }  
}  

第一個?if?循環(huán)（添加左括號）

當?open < max?時，算法會嘗試添加一個左括號到當前的括號組合中（cur.append('(');）。然后，它遞歸地調(diào)用自己（backtrack(...)），在添加了左括號的基礎(chǔ)上繼續(xù)生成括號組合。遞歸調(diào)用返回后，算法需要撤銷剛才添加的左括號，以便在當前的?open?計數(shù)下嘗試添加右括號或其他可能的操作。這就是?cur.deleteCharAt(cur.length() - 1);?在第一個?if?循環(huán)之后的作用。

第二個?if?循環(huán)（添加右括號）

當?close < open?時，算法會嘗試添加一個右括號到當前的括號組合中（cur.append(')');）。與添加左括號的情況類似，它也遞歸地調(diào)用自己，在添加了右括號的基礎(chǔ)上繼續(xù)生成括號組合。遞歸調(diào)用返回后，同樣需要撤銷剛才添加的右括號，以便在當前的狀態(tài)下嘗試其他可能的操作（比如繼續(xù)添加右括號，或者在添加更多左括號之后再次嘗試添加右括號）。因此，cur.deleteCharAt(cur.length() - 1);?也被用在了第二個?if?循環(huán)之后。

總結(jié)

cur.deleteCharAt(cur.length() - 1);?的使用是回溯算法的一個典型特征。它允許算法在嘗試了一條路徑之后，能夠撤銷上一步的操作，并回到之前的狀態(tài)，以便嘗試其他可能的路徑。在生成括號組合的問題中，這確保了算法能夠系統(tǒng)地探索所有可能的括號組合，而不會陷入無限循環(huán)或錯過任何有效的組合。