0141. Parentheses

Input file name: paren.in
Output file name: paren.out
Time limit: 500 ms
Memory limit: 64 megabytes

Generate correct parenthesis sequences in lexicographic order.

Correct parenthesis sequences are given by the rule S ::= ()|(S)|SS

Lexicographic order is imposed by assuming ( less than ).

Input file

Input file contains one integer number n, (1 ≤ n ≤ 10).

Output file

Output all correct parenthesis sequences of length 2n, one sequence a line, without spaces.

Examples:

paren.inparen.out
3((())) (()()) (())() ()(()) ()()()


Source: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version