22. 括号生成
该算法题使用回溯来进行求解为最优，回溯重点为进如递归函数前改一下状态，出来后进行状态还原。复杂回溯可以结合备忘录模式来求解更为复杂的场景。回溯思考过程一般结合树来进行思考。以下是该题的思考过程。
思路一：错误思路
首先我想到的一个非回溯思路1如下：
// 创建一个空的list，用于存储所有满足条件的括号组合Set<String> sets = new HashSet();if (n <= 0)return new ArrayList(sets);sets.add("()");for(int i = 1; i < n; i++){String[] strs = sets.toArray(new String[sets.size()]);sets.clear();// 对于每一个上一次括号组合，根据在每一个元素左边、右边、左右进行添加for (String str:strs){sets.add("()" + str);sets.add(str + "()");sets.add("(" + str + ")");}}return new ArrayList(sets);
以上算法逻辑，1、把"()“加入一个集合sets中。2、复制该集合，并进行遍历，再每一个元素的前面加上”()“，后面加上”()“，元素前加”(“后加”)“。加入sets中进行去重。
该思路有一个明显的错误，会造成缺少某些组合，比如”(())(())"。因为以上策略，无法产生某些对称的组合。
思路二：非最优思路
思路二采用回溯来进行求解，回溯算法擅长于给定一个状态变量，每一次都来对该状态进行改变。
// 方法一：利用左右括号差集来减少回溯 回溯方法求解 n代表单个括号的数量、str代表回溯的位置字符串、diff代表左括号个数 - 右括号个数
public void generateParenthesisByBackTracking(int n, StringBuilder str, int diff){ if(str.length() == n ){if(diff != 0) // 当两个括号相等时，才会加入lists集合return;lists.add(new String(str.toString()));return;}if (diff < n / 2){ // 添加左括号的条件str.append("("); generateParenthesisByBackTracking(n, str, diff + 1);str.deleteCharAt(str.length() - 1);}if(diff > 0){str.append(")");generateParenthesisByBackTracking(n, str, diff - 1);str.deleteCharAt(str.length() - 1);}}
以上思路是没有问题的，但是并非最优，因为在str.length() == n出口判断中，要判断左右括号是否相等，就说明存在部分枝干没有减掉（减枝），导致无效的递归。主要是在diff < n / 2判断处，因为diff代表左右括号数量的差，diff < n / 2减枝不彻底。因此，改进该算法，如下思路三。
加粗样式
该思路不使用diff而是换成left和right来实现。
// 方法二：方法一中，在加入集合前依然要判断左右括号是否相等，说明在回溯过程中减枝不彻底，所以引入方法二 left right机制public void generateParenthesisByBackTracking(int n, StringBuilder str, int left, int right){ if(str.length() == n){lists.add(new String(str.toString()));return;}// 是否加入左括号if(left < n / 2){str.append("("); generateParenthesisByBackTracking(n, str, left + 1, right);str.deleteCharAt(str.length() - 1);}// 是否加入右括号if(left > right){str.append(")"); generateParenthesisByBackTracking(n, str, left, right + 1);str.deleteCharAt(str.length() - 1);}}
此处，在判断left < n / 2时，并非差，而是左括号，因此，将不正确的枝干减掉，没有一次是多余的递归。
