Leetcode刷题——22. 括号生成

题目地址：22. 括号生成

回溯+判断

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

 	static boolean[] used;
    static Stack<Character> stack;
    public static List<String> generateParenthesis(int n) {
    
        List<String> res = new ArrayList<>();
        List<Character> 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<Character> path, List<String> 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<Character> 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<String> res = new ArrayList<>();
    public  List<String> 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）。
直接省去了剪枝，实在厉害。