题目

分析

第一种办法就是将所有的括号的可能情况都列出来，也就是通过递归进行枚举，然后通过方法选择出合适的
第二种方法就是通过深度优选遍历，就是类似二叉树的先序遍历

代码

case1:

public static void main(String[] args) {
        ArrayList<String> res = generateParenthesis(3);
        for(String e:res)
            System.out.println(e);
    }

    public static ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> temp=new ArrayList<>();
        f("",0,n*2,temp);
        ArrayList<String> res=new ArrayList<>();
        for(String e:temp)
        {
            if(isValid(e))
            res.add(e);
            //System.out.println(e);
        }
        return res;
    }

    public static void f(String str,int index,int length,ArrayList<String> res)
    {
         if(str.length()==length){
             res.add(str);
             return ;
         }
         String temp="(";
         f(str+temp,index+1,length,res);
         temp=")";
        f(str+temp,index+1,length,res);
    }

    public static boolean isValid(String str)
    {
        int count=0;
        for(int i=0;i<str.length();i++)
        {
            if(str.charAt(i)=='(')
            {
                count++;
            }else
            {
                count--;
            }
            if(count<0) return false;
        }
        if(count!=0) return false;
        return true;
    }

case2:

public static void main(String[] args) {
        ArrayList<String> res = generateParenthesis(3);
        for(String e:res)
        {
            System.out.println(e);
        }
    }
    public static ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> res=new ArrayList<>();
        f("",0,n,0,0,res);
        return res;
    }

    public static void f(String str,int index,int max,int open,int close,ArrayList<String> res)
    {
        if(index==max*2) res.add(str);
        if(open<max)
        {
            f(str+"(",index+1,max,open+1,close,res);
        }
        if(close<open)
        {
            f(str+")",index+1,max,open,close+1,res);
        }
    }

完成情况

1次