UniLecs #Task. Баланс скобок — 3
Published in
1 min readSep 30, 2019
Задача: Необходимо вывести все правильные скобочные последовательности длины N в лексикографическом порядке.
Входные данные: N — натуральное число от 1 до 10.
Вывод: все правильные скобочные последовательности длины 2N в лексикографическом порядке.
Пример: N = 3
((()))
(()())
(())()
()(())
()()()
Разбор
Задача может быть решена про помощи рекурсивного перебора.
- Будем хранить уже построенный префикс скобочной последовательности.
- Далее выбираем два возможных продолжения этого префикса. Сначала добавляем открывающую скобку и рекурсивно вызываем функцию. Затем к данному префиксу добавляем закрывающую скобку и также рекурсивно вызываем функцию.
- Открывающую скобку можно добавить всегда, если в префиксе было использовано менее n открывающих скобок.
- Закрывающую скобку можно добавить всегда, если в префиксе число открывающих скобок больше, чем число закрывающих.
Если вы хотите более подробно ознакомиться с алгоритмами генерации скобочных последовательностей, то смотрите здесь.
Реализация
Play-test
Протестировать алгоритм вы можете в этой песочнице: