package DP;

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

/**
 * @author dx
 * @version 1.0
 * @date 2022年5月17日 11:04
 * @description: 力扣22 括号生成
 */
public class GenrateParenthesis {
 public static void main(String[] args) {

 List<String> res = new ArrayList<>();
 res = new GenrateParenthesis_Solution().generateParenthesis(3);
 for(String x : res){
 System.out.println(x);
 }
 }
}

class GenrateParenthesis_Solution{
 boolean vis[];
 List<String> res = new ArrayList<>();
 public List<String> generateParenthesis(int n) {
 if(n ==1){
 res.add("()");
 return res;
 }
 vis = new boolean[2*n];
 StringBuffer trace = new StringBuffer();
 char []arr = new char[2*n];
 for(int i = 0;i< n;i++){
 arr[i] = '(';
 arr[2*n-i-1] = ')';
 }
 int index = 0;
 backtrace(res,trace,index,n,arr,vis);
 return res;
 }

 public void backtrace(List<String> res,StringBuffer trace,int index,int n,char []arr,boolean []vis){

 if(index == arr.length && isVaild(trace.toString())){
 res.add(trace.toString());
 return;
 }
 for(int i = 0;i < 2*n;i++){
 if(vis[i] || (i>0 && arr[i-1] == arr[i] && !vis[i-1])){
 continue;
 }
 vis[i] = true;
 trace.append(arr[i]);
 backtrace(res,trace,index+1,n,arr,vis);
 trace.deleteCharAt(index);
 vis[i] = false;

 }
 }
 public boolean isVaild(String s){
 char []arr = s.toCharArray();
 int level = 0;
 for (int i = 0; i < arr.length; i++) {
 if(arr[i] == '('){
 level++;
 }else {
 level--;
 }
 if(level <0){
 return false;
 }
 }
 if(level != 0){
 return false;
 }
 return true;
 }
}