BM60 题解 | #括号生成#

阿哈时刻：

1、output：用StringBuffer,和,String结果不一样，因为没有回溯的机制，所以，必须用 String，每次保持当前递归的值不变。

2、递归过程：就是一个典型的二叉树遍历的过程，这个过程是一个不断，剪枝的过程。如果不剪枝，效果如下：

if(left == n && right == n ) 和 if(left<n) 和 if(right<n && left>right) 就是控制()分配的过程，也是剪枝过程。

通过(left == n && right == n ) 找出了()符号相等的分支，通过(left<n) (right<n)控制了left、right括号的数量，

而，通过 left>right，则控制了(，左括号的优先分配，剪掉了右括号)，先添加的分支。

import java.util.*;


public class Solution {
    
    int stackLevel = 0;
    public ArrayList<String> generateParenthesis (int n) {
        ArrayList<String> res = new ArrayList<String>();
        StringBuffer out = new StringBuffer();  // 不能用，会导致结果一直被用，被重复
                                // 而String+"(" 或者 string+")"每次都会生成一个新实例
        backtrack(0, 0, n, "", res);
        return res;
    }

    public void backtrack(int left, int right, int n, String out,List<String> res) {
        if(left == n && right == n) {
            res.add(out.toString());
            return;
        }

        if(left< n) {
            backtrack(left+1, right, n, out+"(", res);
        } 

        if(right<n && left>right) {
            backtrack(left, right+1, n, out+")", res);
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis2 (int n) {
        ArrayList<String> res = new ArrayList<String>();
        String output = new String();
        backTrack2(0, 0, output,res, n);
        return res;
    }

    void backTrack2(int left, int right, String output, ArrayList<String> res, int n) {
        if(left == n && right == n) {
            res.add(output);
            return;
        }

        if(left< n) {
            backTrack2(left+1, right, output+"(", res, n);
        }

        if(right<n && left>right) {
            backTrack2(left, right+1, output+")", res, n);
        }
    }


}