LeetCode经典易错记录-22. 括号生成

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);
        }
    }