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

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

Дано положительное целое число 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