题解 | 括号生成

import java.util.*;
import java.util.stream.Collectors;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        // 根据左括号数量到达了长度的时候 到达了退出条件 
        // 然后还有就是 连续一个左括号   连续两个左括号  连续 3 个左括号的场景
        // 可以使用回溯找到所有的左括号  然后使用括号的合法性来做校验 来过滤后得到所有的合法 值
        

        char[] num=new char[2*n];
        for(int i=0;i<n;i++){
            num[i]='(';
        }
        for(int i=n;i<2*n;i++){
            num[i]=')';
        }

        boolean[] used = new boolean[num.length];
        ArrayList<String> result = new ArrayList<>();
        LinkedList<Character> trace = new LinkedList<>();
        backtrack(result, used, trace, num);
        return result;
    }




    private void backtrack(ArrayList<String> result, boolean[] used, 
                           LinkedList<Character> trace, char[] num) {
        if (trace.size() == num.length) {
           String ss= trace.stream().map(String::valueOf).collect(Collectors.joining());
            result.add( ss);
            return;
        }
         
        if(trace.size()!=0 && trace.get(0)==')'){
          return;
        }
        for (int i = 0; i < num.length; i++) {
                
            // 剪枝条件：当前数字与前一个相同，且前一个未被使用 => 跳过
            if (used[i]) {
                continue;
            }
       
            // trace 如果左括号数量>右括号数量的时候 才可以使用右括号 

            if (i > 0 && num[i] == num[i - 1] && !used[i - 1]) {
                continue;
            }

            if(num[i]==')'){
                // 必须是左括号数量大于右括号数量 否则继续
                long leftcount=trace.stream().filter(item->String.valueOf(item).equals("(")).count();   
                long rightcount=trace.stream().filter(item->String.valueOf(item).equals(")")).count();             
                 if(leftcount<=rightcount){
                    return;
                }
            }

            used[i] = true;
            trace.add(num[i]);

            System.out.println(i);
            System.out.println(trace);
            backtrack(result, used, trace, num);
            trace.removeLast();
            used[i] = false;
        }
    }

}