UniLecs #Task. Баланс скобок — 3

Задача: Необходимо вывести все правильные скобочные последовательности длины N в лексикографическом порядке.

Входные данные: N — натуральное число от 1 до 10.

Вывод: все правильные скобочные последовательности длины 2N в лексикографическом порядке.

Пример: N = 3
((()))
(()())
(())()
()(())
()()()

Разбор

Задача может быть решена про помощи рекурсивного перебора.

• Будем хранить уже построенный префикс скобочной последовательности.
• Далее выбираем два возможных продолжения этого префикса. Сначала добавляем открывающую скобку и рекурсивно вызываем функцию. Затем к данному префиксу добавляем закрывающую скобку и также рекурсивно вызываем функцию.
• Открывающую скобку можно добавить всегда, если в префиксе было использовано менее n открывающих скобок.
• Закрывающую скобку можно добавить всегда, если в префиксе число открывающих скобок больше, чем число закрывающих.

Если вы хотите более подробно ознакомиться с алгоритмами генерации скобочных последовательностей, то смотрите здесь.

Реализация

C# — рекурсивный алгоритм генерации скобочных последовательностей

Play-test

Протестировать алгоритм вы можете в этой песочнице:

https://dotnetfiddle.net/a2z4eg