寻找合法字符串

	importjava.util.ArrayList;



	importjava.util.List;



	importjava.util.Scanner;



	 



	public class Main{



	 



	    public static void main(String[] args) {



	        Scanner in = newScanner(System.in);



	        intn = in.nextInt();



	        List<String> list = newArrayList<>();



	        DFS(0, 0, n, "", list);



	 



	        for(inti=0;i<list.size()-1;i++){



	            System.out.print(list.get(i)+",");



	        }



	        System.out.println(list.get(list.size()-1));



	    }



	 



	    public static void DFS(intnum1, intnum2, intn, String str, List<String> list) {



	        if(num1==n && num1+num2==2*n) list.add(str);



	        if(num1<n && num1>=num2 && num1+num2<2*n) DFS(num1+1, num2, n, str+'(', list);



	        if(num2<n && num1+num2<2*n) DFS(num1, num2+1, n, str+')', list);



	        return;



	         



	    }



	}

import java.util.*;

#思路是“（）”中间全部间隙添加"()"，完整的左右括号带进去就不会有错序的左右括号。
#例：“1（2）3（4）5”，可以在数字的地方插入完整左右括号"()"，得到其中一些三个括号的结果。以此类推递归下去，结束条件为括号数为所需时不再继续！
#定义一个递归函数，函数使用全局变量（集合筛选掉重复），得到全部后使用列表排序，排好序后使用逗号分隔输出结果
while True:
    try:
        num = int(input())
        result = set()
        def insertBracket(num,now,string):
            brackets = '()'
            if num>now:
                for i in range(0,len(string)):
                    temp = string[:i]+brackets+string[i:]
                    insertBracket(num,now+1,temp)
            elif num==now: 
                global result
                result.add(string)
        insertBracket(num,1,'()')
        result = list(result)
        result.sort()
        print(",".join(result))
    except Exception:
        break

暴力递归

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

#include <bits/stdc++.h>
using namespace std;

void F(int l, int r, string s, vector<string> &v){
    if(l>r)
        return;
    if(l==0 && r==0)
        v.push_back(s);
    if(l)
        F(l-1, r, s+'(', v);
    if(r)
        F(l, r-1, s+')', v);
}

int main(){
    int n;
    scanf("%d", &n);
    string s;
    vector<string> v;
    F(n, n, s, v);
    for(int i=0;i<v.size();i++)
        if(i==v.size()-1)
            cout<<v[i]<<endl;
        else
            cout<<v[i]<<",";
    return 0;
}

/*
作者：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 + ")");
        }
    }
}

import java.math.BigInteger;
import java.util.*;

public class Main {
    private static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); n *= 2;
        dfs(0, 0, "");
        Collections.sort(result);
        boolean flag = true;
        for (String s : result) {
            if (flag) { System.out.printf("%s", s);}
            else { System.out.printf(",%s", s); }
            flag = false;
        }
    }
    private static ArrayList<String> result = new ArrayList<>();
    private static void dfs(int cur, int count, String s) {
        if (cur == n && count == 0) { result.add(s); return;}
        if (n - cur < count) { return; }
        if (count > 0) { dfs(cur+1, count-1, s+")");}
        dfs(cur+1, count+1, s+"(");
    }
}

// 字典序就是优先放左括号(
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        br.close();
        StringBuilder res = new StringBuilder();
        backTrace(n,0,0,"",res);
        System.out.println(res.substring(1));
    }
    private static void backTrace(int n, int leftBracket, int rightBracket, String tmp, StringBuilder res){
        if(rightBracket > leftBracket) return;
        if(leftBracket > n) return;
        if(rightBracket == n) {res.append(','); res.append(tmp); return;}
        backTrace(n,leftBracket+1,rightBracket,tmp+"(",res);
        backTrace(n,leftBracket,rightBracket+1,tmp+")",res);
    }
}

#include<bits/stdc++.h>
#define sum  (n<<1)
using namespace std;
vector<string >res;
string path;
int n;
void dfs(int len,int L,int R) {
    if(L <  R || len > sum || sum -L <R    ) return ;
    if(len  == (n<<1)) {
       if(L==R) res.push_back(path);
    }else {
        if(L==R) {
           //只能加左边括号 
            path.push_back('(');
            dfs(len+1,L+1,R);
            path.pop_back();
            
        }else {
            //l>r , 加左边 或者右边
            path.push_back('(');
            dfs(len+1,L+1,R);
            path.pop_back();
            path.push_back(')');
            dfs(len+1,L,R+1);
            path.pop_back();
        }
    }
}
int main(void) {
    
    cin>>n;
    dfs(0,0,0);
    for(int i=0;i<res.size()-1;++i) cout << res[i]<<",";
    cout << res.back()<<endl;
}

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;
	}
    }
}

def symbol(left,right,temp,ans):
    if left == 0 and right == 0:
        ans.append(temp[:])
        return ans
    #添加括号，一定先添加左括号，再添加右括号
    if left:
        symbol(left - 1,right,temp + '(',ans)
    if left < right:
        symbol(left,right - 1,temp + ')',ans)
    
while True:
    try:
        n = int(input())
        ans = []
        symbol(n,n,'',ans)
        ans.sort()
        print(','.join(ans))
    except:
        break

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

public class Main_02 {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        List<String > list=new ArrayList<>();
        help(n,n,"",list);
        for(int i=0;i<list.size()-1;i++){
            System.out.print(list.get(i)+",");
        }
        System.out.println(list.get(list.size()-1));
    }

    public static void help(int left,int right,String out,List<String > list){
        if(left<0||right<0||left>right){
            return;
        }
        if(left==0 && right==0){
            list.add(out);
            return;
        }
        help(left-1,right,out+"(",list);
        help(left,right-1,out+")",list);
    }
}

void dfs(int n, char c, int left, int right) {
    vec.push_back(c);//每一层搜索完必会回溯，所以这一步放在最开头，
//反正最终都会回溯被pop
    if (left < right) {//left为当前左括号数目，right为右括号数目
        return;//保证搜索中的每一步，左括号比右括号多
    }
    if (n == 2 * num) {
        ans++;
        getSeq();
        return;
    }
    //这两步同一般回溯法，只是不同情况传入
    //字符不同，同时当有一种情况达到指定次数时候，该情况淘汰，
    //深度搜索用另一个方式进行
    if (left < num) {//因为从第0层开始的，所以这里不能 '='
        dfs(n + 1, '(', left + 1, right);
        vec.pop_back();
    }
    if (right < num) {
        dfs(n + 1, ')', left, right + 1);
        vec.pop_back();
    }
}

int main() {
    cin >> num;
    dfs(0, '\0', 0, 0);//从第0层开始，最开始插入一个不影响结果的字符
    cout << '\n';
}

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

public clas***ain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int lcount = n - 1;
        int rcount = n;

        List<String> res = new ArrayList<>();
        dfs(res,lcount,rcount,"(");

        for (int i = 0; i < res.size(); i++) {
            if (i != res.size() - 1) {
                System.out.print(res.get(i) + ",");
            } else System.out.println(res.get(i));
        }

    }

    static void dfs(List<String> res, int lcount, int rcount, String s) {
        if ((rcount == 0 && lcount > 0) || rcount < 0 || lcount < 0 || (lcount > rcount)) {
            return;
        }
        if (rcount == 0 && lcount == 0) {
            res.add(s);
        }

        dfs(res,lcount - 1, rcount, s + "(");
        dfs(res,lcount,rcount - 1, s + ")");
    }
}

n = int(input())
if n == 1:
    print('()')
    exit()
res = ['()']
while n > 1:
    newres = set()
    for s in res:
        cands = []
        for i in range(len(s)):
            if s[i] == '(':
                cands.append(i)
        cands.append(len(s))
        for i in range(len(cands)):
            for j in range(len(cands)-1, i-1, -1):
                newres.add(s[:i] + '(' + s[i:j] + ')' + s[j:])
    res = newres
    n -= 1
print(','.join(sorted(res)))