题解 |找到规律后的简单做法

public ArrayList<String> generateParenthesis (int n) {
        ArrayList<String> arr=new ArrayList<>();
        if(n==0) return null;
        // write code here
        //合法括号 不以)开头，不以(结尾
        //即()开头结尾
        //消去几个（）后，仍应该保持这个性质,比如())不行
        //一个合法序列插入另一个合法序列任意位置仍然合法
        //问题转化成，从一个括号开始，用其他括号慢慢插
        String init="()";
        if(n==1){
            arr.add(init);
            return arr;
        }
        HashSet<String> set=new HashSet<>();
        ArrayList<String> lastRes=generateParenthesis(n-1);
        for(String item:lastRes){
                        //可插入空位个数枚举,2(n-1)+1=2n-1
            for(int i=0;i<2*n-1;i++){
                String prefix;
                if(i==0) prefix="";
                else prefix=item.substring(0,i);
                
                String end;
                if(i==2*n-2) end="";
                else end=item.substring(i);
                set.add(prefix+"()"+end);
            }
        }
        for(Iterator<String> it=set.iterator();it.hasNext();){
            arr.add(it.next());
        }
        return arr;
}