Несколько алгоритмов генерации правильных скобочных последовательностей:

1. Рекурсивный алгоритм получения лексикографического порядка. 1 Позволяет вывести все правильные скобочные последовательности в лексикографическом порядке с заданным количеством открывающихся скобок. 1 Для этого перебираются все возможные варианты последующих скобок для каждого возможного префикса. 1
2. Генерация следующей скобочной последовательности. 1 Если известна строка s, представляющая собой правильную скобочную последовательность, то алгоритм выводит следующую скобочную последовательность, а если её нет, то выводит «No solution». 1 Для этого нужно найти последнюю открывающуюся скобку, которую можно заменить, заменить её на закрывающуюся, а оставшиеся в конце скобки (если они есть) заменить на минимально возможную последовательность скобок. 1
3. Алгоритм на основе динамического программирования. 2 Для каждого количества скобок, из которых состоит последовательность, хранится множество возможных вариантов. 2 Для получения новых последовательностей из каждого предыдущего множества используется определённый алгоритм. 2
4. Алгоритм с использованием стека. 4 В цикле, если встречается открывающаяся скобка, её кладут на стек. 4 Если встречается закрывающаяся скобка, то её сравнивают с последним элементом в стеке. 4 Если скобки совпадают, то открывающую скобку вынимают из стека. 4 Если скобки не совпадают, сразу возвращают false из функции — последовательность неправильная. 4 После завершения цикла проверяют, что стек пустой и все скобки совпали попарно. 4