Алгоритмы и структуры данных

Скобочные последовательности

Дано положительное целое число n. Необходимо сгенерировать все корректные скобочные последовательности длины 2n и вывести их в лексикографическом порядке.

Определение корректной скобочной последовательности:

  • Пустая строка считается корректной скобочной последовательностью.

  • Если S — корректная скобочная последовательность, то (S) также является корректной скобочной последовательностью.

  • Если A и B — корректные скобочные последовательности, то их конкатенация AB тоже является корректной скобочной последовательностью.

Входные данные

На вход подается одно целое число n (1 ≤ n ≤ 11).

Выходные данные

Выведите все корректные скобочные последовательности длины 2n, каждую в отдельной строке. Последовательности должны быть выведены в лексикографическом порядке.

Пример

Вход

Выход

3

((()))
(()())
(())()
()(())
()()()

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 7 MB

To check your solution you need to sign in
Sign in to continue