Рита по поручению Тимофея наводит порядок в правильных скобочных последовательностях (ПСП), состоящих только из круглых скобок (). Для этого ей надо сгенерировать все ПСП длины 2n в алфавитном порядке —– алфавит состоит из ( и ) и открывающая скобка идёт раньше закрывающей.
Помогите Рите —– напишите программу, которая по заданному n выведет все ПСП в нужном порядке.
Рассмотрим второй пример. Надо вывести ПСП из четырёх символов. Таких всего две:
- (())
- ()()
(()) идёт раньше ()(), так как первый символ у них одинаковый, а на второй позиции у первой ПСП стоит (, который идёт раньше ).
На вход функция принимает n — целое число от 0 до 10.
Функция должна напечатать все возможные скобочные последовательности заданной длины в алфавитном (лексикографическом) порядке.
|
3
|
((())) (()()) (())() ()(()) ()()() |
|
2
|
(()) ()() |