1663. Bracket sequences

 

Positive integer n (1 ≤ n ≤ 10) is given. Print in alphabetical order all correct bracket sequences of length 2n, assuming that the character '(' comes before ')' in the alphabet.

A correct bracket sequence is either an empty string, or a string like (S), where S is a correct bracket sequence, or a string like S1S2, where S1 and S2 are correct bracket sequences.

 

Input. One integer n (0 ≤ n ≤ 10).

 

Output. Print in alphabetical order all correct bracket sequences of length 2n, one sequence per line, without spaces.

 

Sample input

Sample output

3

((()))

(()())

(())()

()(())

()()()

 

 

SOLUTION

combinatorics

 

Algorithm analysis

Solve the problem by exhaustive search. Let s be a string where we’ll generate the required sequences. It is initially empty. Let the variables left and right contain the number of unused open and closed parentheses, respectively (initially left = right = n). Then:

·        If left > 0, we can append ‘(‘ to the string s.

·        If left < right, we can append ‘)‘ to the string s. The number of already used open parentheses should not be less than the number of closed ones.

When left = right = 0, print the next correct bracket sequence.

 

Algorithm realization

Function gen generates the sequences. Part of the already generated bracket sequence is contained in string s. The variables left and right contain the number of unused open and closed parentheses, respectively.

 

void gen(string s, int left, int right)

{

  if (left == 0 && right == 0)

  {

    cout << s << endl;

    return;

  }

 

  if (left > 0)     gen(s + "(", left - 1, right);

  if (left < right) gen(s + ")", left, right - 1);

}

 

The main part of the program. Read the value of n and start generating the bracket sequences.

 

cin >> n;

gen("",n,n);