Рита по поручению Тимофея наводит порядок в правильных скобочных последовательностях (ПСП), состоящих только из круглых скобок (). Для этого ей надо сгенерировать все ПСП длины 2n в алфавитном порядке – алфавит состоит из ( и ) и открывающая скобка идёт раньше закрывающей.
Помогите Рите – напишите программу, которая по заданному n выведет все ПСП в нужном порядке.
Рассмотрим второй пример. Надо вывести ПСП из четырёх символов. Таких всего две:
(())
()()
(()) идёт раньше ()(), так как первый символ у них одинаковый, а на второй позиции у первой ПСП стоит (, который идёт раньше ).
Формат ввода
На вход функция принимает n — целое число от 0 до 10.
Формат вывода
Функция должна напечатать все возможные скобочные последовательности заданной длины в алфавитном (лексикографическом) порядке.
def gen_binary(control, n1, n2, prefix): if n1 == 0 and n2 == 0: print(prefix) else: if n1 > 0: gen_binary(control + 1, n1 - 1, n2, prefix + '(') if (control > 0 and n2 > 0): gen_binary(control - 1, n1, n2 - 1, prefix + ')') n = int(input()) control = 0 n1 = n n2 = n gen_binary(control, n1, n2, '')
Ваш код генерит все последовательности скобок. А надо только ПСП. Во втором if надо добавить если n1 < n2