// Arup Guha
// 10/6/05
// Solution to COP 3530 Recitation #5 Problem A: Parentheses.

import java.io.*;

public class paren {

  public static void main(String[] args) throws IOException {

    BufferedReader stdin = new BufferedReader
				(new InputStreamReader(System.in));

    System.out.println("Would you like to print parentheses?(y/n)");
    char c = (stdin.readLine()).charAt(0);

    // Loop until user wants to quit.
    while (c == 'y' || c == 'Y') {

      // Get the user input.
      System.out.println("What value of n would you like to try?");
      int n = Integer.parseInt(stdin.readLine());

      // Don't try invalid cases.
      if (n < 1) {
        System.out.println("Sorry that is invalid.\n");
        continue;
      }

      // Print out the output.
      System.out.println("Here is your output:");
      print(n);
      System.out.println();

      // See if they want to try this again.
      System.out.println("Would you like to print parentheses again?(y/n)");
      c = (stdin.readLine()).charAt(0);

    }

  }

  // Wrapper function for the recursive function that does the printing.
  public static void print(int n) {

    // We start the buffer with nothing, needing to add n open parens
    // and n closed parens.
    printAll("", n, n);
  }

  // Prints out all the combinations of concatenating the buffer to 
  // num_open open parentheses and num_close closing parentheses. In
  // order to work the number of open parentheses in the buffer plus
  // num_open should equal the number of close parentheses in the buffer
  // plus num_close.
  public static void printAll(String buffer, int num_open, int num_close) {


    // No new parens to add to the buffer. Print out the completed buffer.
    if (num_open == 0 && num_close == 0) {
      printBuffer(buffer);
      return;
    }

    // All buffers are invalid that have more close parens than open
    // parens in the beginning. (This states that there are more open
    // parentheses to add to the end than close parentheses.
    if (num_open > num_close)
      return;

    // Equal number of open and close parens have been used, we MUST add
    // an open paren next.
    if (num_open == num_close) {

      // Add the open paren to the buffer and then we have one less one
      // to add in the recursive call.
      printAll(buffer+"{", num_open-1, num_close);
      return;
    }

    // If we get here, we have more close parens than open parens. As long
    // as we have an open paren left to add, try this possibility out.
    if (num_open > 0)
      printAll(buffer+"{", num_open-1, num_close);

    // We can definitely add a close paren if we get here. Try it!
    printAll(buffer+"}", num_open, num_close-1);
    
  }

  // This prints out the buffer with spaces after every character.
  public static void printBuffer(String buffer) {

    int i;
    for (i=0; i<buffer.length(); i++)
      System.out.print(buffer.charAt(i)+" ");
    System.out.println();
  }

}