寻找合法字符串

暴力递归

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
    static ArrayList<String> list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        dfs("", n, n);
        for(int i = 0; i < list.size(); i++){
            if(i < list.size() - 1){
                System.out.print(list.get(i) + ",");
            }else{
                System.out.println(list.get(i));
            }
        }
    }
    
    public static void dfs(String path, int restL, int restR) {
        if(restR < restL){
            // 到目前为止追加了过量的右括号在左括号的左边，本次搜索无效
            return;
        }else if(restL == restR){
            // 左右两括号相等时追加左括号
            if(restL > 0){
                dfs(path + "(", restL - 1, restR);
            }else{
                list.add(path);
            }
        }else{
            // restR>restL 可以追加左括号，也可以追加右括号
            if(restL > 0){
                // 先尝试追加左括号以保证字典序
                dfs(path + "(", restL - 1, restR);
                dfs(path + ")", restL, restR - 1);
            }else{
                dfs(path + ")", restL, --restR);
            }
        }
    }
}

public class Main{
    private static Set<String> set=new TreeSet<>();
    private static int sM=0;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        sM=sc.nextInt();
        outPrint(1,"()");
        String str="";
        for(String s:set){
            str=str+s+",";
        }
        System.out.println(str.substring(0,str.length()-1));
        sc.close();
    }
    public static void outPrint(int index,String str) {
	if(index==sM)
	    set.add(str);
	for(int i=index;i<sM;) {
	    for(int j=0;j<str.length();j++) {
		outPrint(i+1,str.substring(0,j)+"()"+str.substring(j));
	    }
	    break;
	}
    }
}

/*
作者：sweetiee
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/jian-dan-dfsmiao-dong-by-sweetiee/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
力扣上的解法dfs搜索，n对括号，按照条件每次搜索增加左括号或者右括号
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main{
    static ArrayList<String> list = new ArrayList<>();
    public static void main(String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dfs(n,n,"");
        for(int i = 0;i<list.size();i++){
            System.out.print(list.get(i));
            if(i<list.size() - 1)
                System.out.print(",");
        }
    }
    //dfs搜索
    public static void dfs(int left,int right,String curstr){
        if(left==0 && right==0){
            list.add(curstr);
            return;
        }
        
        if(left>0){//左括号还有剩余就往里面拼接左括号,因为括号是先左后右，优先拼接左
            dfs(left-1,right,curstr + "(");
        }
        if(right>left){//如果右括号剩余量大于左括号，这时就需要添加右括号了，不然该字符串一定不是有效的
            dfs(left,right-1,curstr + ")");
        }
    }
}