捕获3.PNG

看到题目第一个想到的解法是dp，那么就要找规律了
n=1 result : ()
n=2 result : (())，()()
n=3 result : ((()))，(()())，()(())，(())()，()()()
那么规律就是每一次都比上一个数需要多一加一个左侧"()"+pre(n-1)，右侧pre(n-1)+"()"，包围"("+pre+")"，但是需要注意的是左侧和右侧凡是遇到()()...这样的会重复，需要特殊注意，可以通过set去重，但是我没有选择，因为还需要转换，所以代码如下

public class generateParenthesis {
    public static List<String> generateParenthesis(int n) {
        List<String> l = new ArrayList<>();
        if(n==1){
            l.add("()");
            return l;
        }else if(n==2){
            l.add("(())");
            l.add("()()");
            return l;
        }else {
            List<String> temp = generateParenthesis(n-1);
            for(int i=0;i<temp.size();i++){
                l.add("("+temp.get(i)+")");
                if(i!=temp.size()-1){
                    l.add("()"+temp.get(i));
                    l.add(temp.get(i)+"()");
                }
            }
            l.add(temp.get(temp.size()-1)+"()");
        }
        return l;
    }

    public static void main(String[] args) {
        List<String> l = generateParenthesis(4);
        for(int i=0;i<l.size();i++){
            System.out.println(l.get(i));
        }
    }
}