0141. Parentheses

Имя входного файла:	paren.in
Имя выходного файла:	paren.out
Ограничение по времени:	500 ms
Ограничение по памяти:	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.in	paren.out
3	((())) (()()) (())() ()(()) ()()()

Источник: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Автор: Andrew Lopatin, Nick Durov

Обсудить       Отправить решение