AtCoder. 002 Encyclopedia of Parentheses(3)

import java.util.*;
import java.io.*;

public class Main{
  static int n;
  static StringBuilder sb = new StringBuilder();
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    if(n%2 == 1) return;

    char[] charArr = new char[n];
    bfs(charArr, 0, 0, 0);
    System.out.println(sb.toString());
  }

  static void bfs(char[] charArr, int index, int open, int close) {
    if(index == n) {
      sb.append(new String(charArr)).append("\n");
      return;
    }
    if(open < n/2 && close < n/2) {
      charArr[index] = '(';
      open++;
      bfs(charArr, index + 1 , open, close);
      open--;
      if(open > close) {
        charArr[index] = ')';
        close++;
        bfs(charArr, index + 1 , open, close);
        close--;
      }
    } else if(open == n/2) {
      for(int i = index; i < n; i++) charArr[i] = ')';
      bfs(charArr, n, n/2, n/2);
    }
  }
}