Leetcode brushing questions - 22. Bracket generation

题目地址：22. 括号生成

回溯+判断

Talk about your own ideas first,The first thing you see when you see a question like this is backtracking,My idea is to find all parenthesis combinations first,Then determine whether it meets the requirements of the subject.
Find parenthesis combinations similar to47. 全排列 II
要考虑的东西比较多,Take a good look at it when you go back and refresh the backtracking.
In addition, the stack is used to judge whether it meets the requirements,是20. 有效的括号的简单版
还有就是将listConverted to string is usedjdk8新特性
path.stream().map(String::valueOf).collect(Collectors.joining())
mapis to operate on each element,collectIs the conversion of data collections into objects.
下面是代码：

 	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];
        //Constructs an array of parentheses
        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;
            }
            //A small pruning
            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;
    }

The code is bloated and inefficient,It's a simple idea,It's unlikely to be written in an interview.
After reading the comment area, I got another recursive idea,如下

递归

Think about our needs,其实可以转换成,The opening parenthesis appears before the closing parenthesis,When both the left and right parentheses become n时,The recursion is complete.

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

The idea of ​​the code is,When the left parenthesis is still there,Open parentheses are preferred（第二个if）,As long as there are currently more left parentheses than right parentheses,You can put the right parenthesis（第三个if）.
Just skip the pruning,实在厉害.