LCR 085. 括號生成 - 力扣（LeetCode）

一. 根據題意，分析出符合要求的括號組合需要滿足以下兩個條件：

1. 左括號數或者右括號數都不能超過 n；

2. 從最左側開始的每一個子集，不可以出現右括號數大于左括號數，例如："( () ) ) (" 的子集："( () ) ) "就出現了右括號書大于左括號數，這樣是不符合規范的；

二. 畫決策圖來分析遞歸過程：?

以下圖中的"左括號"和"右括號"指的是他們的數量！

?三. 考慮全局變量的使用：

1. 使用全局變量 StringBuffer 來存儲遍歷過程的值；

2. 使用全局變量 List<String> 來存儲每一次滿足結果的String；

3. 使用全局變量 left 和 right 來存儲當前使用的左括號和右括號的數量；

所以遞歸出口可以設置為 StringBuffer.length() == 2*n ；

四. 針對上述提到的兩個條件來進行剪枝操作；

1. 右括號數小于左括號書的時候，才進行右括號數的添加：right <?left；

2. 左括號數和右括號數量小于n的時候，才進行添加；left < n；right < n；

?

四. 回溯過程：

當決策數在每一層進行左括號或者右括號添加完成之后，需要進行現場恢復操作，也就是把 StringBuffer 的最后一個字符刪除；

代碼實現：?

class Solution {List<String> ret = new ArrayList<>();StringBuffer str = new StringBuffer();int left = 0;int right = 0;public List<String> generateParenthesis(int n) {dfs(n);return ret;}public void dfs(int n){// 遞歸出口if(str.length() == n*2){ret.add(str.toString());return;}// 通過剪枝，符合條件的來添加左括號if(left < n){str.append("(");left++;dfs(n);// 回溯str.deleteCharAt(str.length()-1);left--;}// 通過剪枝，符合條件的來添加右括號if(right < left && right < n){str.append(")");right++;dfs(n);// 回溯str.deleteCharAt(str.length()-1);right--;}}
}