Код Senior Перебор с возвратом обновлено
Правильные скобочные последовательности
Условие
Все правильные последовательности из n пар скобок, в лексикографическом порядке (открывающая раньше закрывающей).
Примеры
generateParenthesis(3) // ["((()))", "(()())", "(())()", "()(())", "()()()"]
generateParenthesis(1) // ["()"]
generateParenthesis(0) // [""]
Как подойти
Два простых условия гарантируют корректность на каждом шаге, поэтому проверять готовую строку не нужно вовсе. Это и есть суть отсечения: не порождать неправильные ветки вместо того, чтобы отбрасывать их в конце.
Подсказки: 2
- Открывающую можно ставить, пока их меньше n.
- Закрывающую - только если открытых больше, чем закрытых.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.