捕获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));
}
}
}
