力扣——22. 括号生成

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class p22括号生成 {
    /**
     * 方法一：
     * 我们可以生成所有 4^n个 '(' 和 ')' 字符构成的序列，然后我们检查每一个是否有效即可。
    * */
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        char[] chars = new char[2*n];
        GetAll(chars,0,result);
        return result;
    }
    public void GetAll(char[] chars,int pos,List<String> result){
        if(pos == chars.length){
            if (TString(chars)) result.add(new String(chars));
        }else {
            chars[pos]='(';
            GetAll(chars,pos+1,result);
            chars[pos]=')';
            GetAll(chars,pos+1,result);
        }
    }
    public boolean TString(char[] chars){
        int num=0;
        for (char c : chars){
            if(c=='('){
                num++;
            }else if(c==')'){
                num--;
            }
            if (num<0) return false;
        }
        if (num == 0) return true;
        else return false;
    }
    /**
     * 方法二：
     * 我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，
     * 如果左括号数量不大于 nnn，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
     * */
    public List<String> generateParenthesisS(int n){
        List<String> result = new ArrayList<>();
        GetPlus("",0,0,n,result);
        return result;
    }

    private void GetPlus(String s, int left, int right, int n,List<String> result) {
        if (s.length() == 2*n){
            result.add(s);
            return;
        }
        if(left<n){
            GetPlus(s+"(",left+1,right,n,result);
        }
        if (right<left){
            GetPlus(s+")",left,right+1,n,result);
        }
    }

    /**
     * 方法三：
     * */
    public List<String> generateParenthesisT(int n) {
        List<String> result = new ArrayList<>();
        char[] chars = new char[2*n];
        GetTwo("",n,n,result);
        return result;
    }
    public void GetTwo(String str,int left,int right,List<String>list){
        if(left==0&&right==0){
            list.add(str);
            return;
        }
        if (left==right){
            //剩余左右括号数相等，下一个只能用左括号
            GetTwo(str+"(",left-1,right,list);
        }else if (left<right){
            //剩余左括号小于右括号，下一个可以用左括号也可以用右括号
            if (left>0){
                GetTwo(str+"(",left-1,right,list);
            }
            GetTwo(str+")",left,right-1,list);
        }
    }

    @Test
    public void Main()
    {
/*        List<String> list = generateParenthesis(3);
        for (String s : list){
            System.out.println(s);
        }
        List<String> list1 = generateParenthesisT(3);
        for (String s : list1){
            System.out.println(s);
        }*/
        List<String> list2 = generateParenthesisS(3);
        for (String s : list2){
            System.out.println(s);
        }
    }

}