Leetcode刷题——22. 括号生成

题目地址：22. 括号生成

先说说自己的思路，看到这类题目第一眼就是回溯，我的想法就是先找到所有的括号组合，然后再判断是否符合题目的要求。
找括号组合类似于47. 全排列 II
要考虑的东西比较多，回头重刷回溯的时候再好好回顾。
另外判断是否符合要求用的是栈，是20. 有效的括号的简单版
还有就是将list转换为字符串用的是jdk8新特性
path.stream().map(String::valueOf).collect(Collectors.joining())
map是对每个元素进行操作，collect是将数据收集转换成对象。
下面是代码：

 	static boolean[] used;
    static Stack stack;
    public static List generateParenthesis(int n) {
        List res = new ArrayList<>();
        List path  =new ArrayList<>();
        used = new boolean[n*2];
        char[] nums = new char[n * 2];
        //构造括号的数组
        for (int i = 0; i < n; i++) {
            nums[i]='(';
            nums[i+ n]=')';
        }
        //回溯
        backtrack(path,res,2*n,nums);
        return res;
    }

    private static void backtrack( List path, List res,int len,char[] nums) {
        if(path.size() >= len ){
            if(judge(path)){
                res.add(path.stream().map(String::valueOf).collect(Collectors.joining()));
            }
            return;
        }
        //for 是每一行，
        //backbrack是每一层
        for (int i = 0; i < len; i++) {
        	//去重
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            //一个小小的剪枝
            if(path.size()==0 && nums[i]==')'){
                continue;
            }
            if (!used[i]) {
                used[i] = true;
                path.add(nums[i]);
                backtrack( path, res, len, nums);
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }
	//判断括号
    private static boolean judge(List path) {
        stack = new Stack<>();
        stack.clear();
        for (Character character : path) {
            if(character == '(') {
                stack.push(character);
            }
            else if(character == ')'){
                if(stack.isEmpty()) {
                    return false;
                }
                else {
                    stack.pop();
                }
            }
        }
        return stack.size() == 0;
    }

代码臃肿且效率差，就是思路简单，要在面试写出来不太可能。
看了评论区之后得到了另一种递归的思想，如下

想一想我们的需求，其实可以转换成，左括号要比右括号先出现，当左右括号都变为n时，就完成了递归。

 	List res = new ArrayList<>();
    public  List generateParenthesis2(int n) {
        dfs(n,n,"");
        return res;
    }
    //为什么能用String，因为是不可变类型，不会牵一发而动全身
     void dfs(int left,int right,String cur){
        if (left==0 && right == 0){
            res.add(cur);
        }
        if(left>0){
            dfs(left-1,right,cur+"(");
        }
        if(left>right){
            dfs(left,right-1,cur+")");
        }
    }

代码的思路就是，当左括号还有时，优先放左括号（第二个if），只要当前左括号的数量比右括号多，就可以放右括号（第三个if）。
直接省去了剪枝，实在厉害。