题解 | #括号生成#

典型回溯算法的一个模版套用
针对回溯算法，大部分算法均可采用两种模版去做
backtrack(params) {
   if(终止条件){
      收集结果集
	  return;
   }
   for(int i = 0/cur; i < n;i++) {
      记录结果集
	  backtrack(params);
	  // 回溯
	  结果集回溯
   }
}
// 上面这个模版适用于对排列、组合等题型
但是对回溯算法还有另外一个经典的适用场景，比如子集问题，这类算法有一个共同点，就是对元素的使用条件有要求，不可以重复，且存在一定的剪枝过程。针对于这种特征，回溯的另外一种模版可以解决此类的问题
backtrack(params) {
   if(终止条件){
      收集结果集
	  return;
   }
   记录结果集
   backtrack(params);
   // 回溯
   结果集回溯
   // 在一些特殊情况下，可能还需要选择当前元素，因此可能会有再次dfs的过程
   // backtrack(params);
}

括号生产明显就是一个子集问题的一个衍生，在生成的括号中，可能存在非法的括号，因此需要将其排除，因此下列算法的check方法就是判断生成的字符是否符合规则




import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        ArrayList<String> res = new ArrayList<String>();
        backtrack(n, 0, 0 , new StringBuilder(), res);
        return res;
    }

    public void backtrack(int n, int open, int close, StringBuilder str, ArrayList<String> res) {
        if (2 * n == str.length()) {
            if(check(str.toString())) {
                res.add(str.toString());
            }
            return;
        }
        if (open < n) {
            str.append("(");
            backtrack(n, open + 1, close, str, res);
            str.deleteCharAt(str.length() - 1);
        }
        if (close < n) {
            str.append(")");
            backtrack(n, open , close + 1, str, res);
            str.deleteCharAt(str.length() - 1);
        }
    }

    public boolean check(String str) {
        Deque<Character> stack = new LinkedList<>();
        for (char ch : str.toCharArray()) {
            if (ch == ')') {
                if (stack.isEmpty() || stack.pop() != '(') {
                    return false;
                }
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}