Алгоритм лексикографического перечисления правильных скобочных последовательностей работает следующим образом: 24

1. Находится крайняя правая открывающая скобка, которую можно заменить закрывающей скобкой, чтобы получить лексикографически увеличенную строку скобок. 4
2. Оставшаяся часть строки заполняется лексикографически минимальной. 4 То есть сначала как можно большим количеством открывающих скобок, а затем заполняются оставшиеся позиции закрывающими скобками. 4 Другими словами, оставляется без изменения как можно более длинный префикс исходной последовательности, а в суффиксе эта последовательность заменяется на лексикографически минимальную. 24
3. Чтобы найти эту позицию, перебирают символ справа налево и сохраняют баланс глубины открывающих и закрывающих скобок. 4 Когда встречают открывающую скобку, уменьшают глубину, а когда закрывающую — увеличивают её. 4
4. Если в какой-то момент встречают открывающую скобку, а баланс после обработки этого символа положительный, значит, нашли крайнюю правую позицию, которую можно изменить. 4 Меняют символ, вычисляют количество открывающих и закрывающих скобок, которые нужно добавить с правой стороны, и упорядочивают их лексикографически минимальным образом. 4
5. Если не находят подходящей позиции, то эта последовательность уже является максимально возможной, и ответа нет. 4

Таким образом, алгоритм перебирает все возможные варианты последующих скобок для каждого возможного префикса, что и позволяет получить все возможные правильные скобочные последовательности в лексикографическом порядке. 1