題目鏈接

/**

? ? ? ? ? ? 合法括號生成規則:

? ? ? ? ? ? ? ? ? ? ? ? ? ? 第一個括號必須是左括號(第一個為右必定無法閉合)

? ? ? ? ? ? ? ? ? ? ? ? ? ? 選擇過程中左括號數量必須小于n才可選擇左括號(大于n則一定有括號無法閉合)

? ? ? ? ? ? ? ? ? ? ? ? ? ? 左括號數量必須大于右括號數量才可選擇右括號(相等代表所有前驅括號都已閉合)

? ? ? ? ? ? 所需參數:

? ? ? ? ? ? ? ? ? ? ? ? ? ? left 記錄已選擇左括號數

? ? ? ? ? ? ? ? ? ? ? ? ? ? right 記錄已選擇右括號數

? ? ? ? ? ? 限制條件:

? ? ? ? ? ? ? ? ? ? ? ? ? ? 由于括號必定從左括號開始的特性,左括號優先級高于右括號

? ? ? ? ? ? ? ? ? ? ? ? ? ? left < n --> 避免左括號超量,導致無足夠右括號與之閉合

? ? ? ? ? ? ? ? ? ? ? ? ? ? left > right --> 括號未全部閉合,可選擇右括號與之閉合

? ? ? ? ? ? ? ? ? ? ? ? ? ? 兩條件共同保證括號生成合法性 ? ? ? ? ? ? ?

*/

class Solution {//保存結果集private List<String> res = new ArrayList<>();//保存單次結果private StringBuilder tempResult = new StringBuilder();private int n;public List<String> generateParenthesis(int n) {/**合法括號生成規則:第一個括號必須是左括號(第一個為右必定無法閉合)選擇過程中左括號數量必須小于n才可選擇左括號(大于n則一定有括號無法閉合)左括號數量必須大于右括號數量才可選擇右括號(相等代表所有前驅括號都已閉合)所需參數:left 記錄已選擇左括號數right 記錄已選擇右括號數限制條件:由于括號必定從左括號開始的特性,左括號優先級高于右括號left < n --> 避免左括號超量,導致無足夠右括號與之閉合left > right --> 括號未全部閉合,可選擇右括號與之閉合兩條件共同保證括號生成合法性              */this.n = n;backtrack(0,0);return res;}private void backtrack(int left, int right) {//生成完畢,保存結果if(left + right == 2*n) {res.add(tempResult.toString());return;}//左括號未到上限可選擇左括號if(left < n) { tempResult.append("(");left++;backtrack(left,right);//回溯left--;tempResult.deleteCharAt(tempResult.length() - 1);}//左括號未全部與右括號匹配,可選擇右括號if(left > right) {tempResult.append(")");right++;backtrack(left,right);//回溯right--;tempResult.deleteCharAt(tempResult.length() - 1);}}
}