day-20 括号生成

思路:用dfs遍历所有的可能的括号组合，再通过istrue（）方法判断是否合法

code:

class Solution {

    List<String> ans=new ArrayList<>();
    public List<String> generateParenthesis(int n) {

        int l=n,r=n;
        String s="";
        dep(s,l,r);
        return ans;
    }
    public void dep(String s,int l,int r){

        if(l==0&&r==0){

            if(istrue(s))
            ans.add(s);
        }else{

            if(l!=0){

                String ts=s+'(';
                dep(ts,l-1,r);
            }
            if(r!=0){

                String ts=s+')';
                dep(ts,l,r-1);
            }
        }
    }
    public boolean istrue(String s){

        int len=s.length();
        int ans=0;
        for(int i=0;i<len;i++){

            if(s.charAt(i)=='('){

                if(ans>0) return false;
                ans--;
            }else{

                if(ans>=0) return false;
                else{

                    ans++;
                }
            }
        }
        if(ans!=0) return false;
        return true;
    }
}

原文链接: https://blog.csdn.net/qq_53568730/article/details/136736431