Где применяется
1. Задача
Подмножества, перестановки и сочетания мы перебирали: пробовали каждую ветку и оставляли те, что дошли до конца. Отсечка в прошлом уроке смотрела только на количество: хватит ли оставшихся элементов. Теперь отсекать будем по правилу. Ветку бросают в тот момент, когда она нарушила ограничение, задолго до конца. Тогда силы не уходят на достройку расстановки, которая всё равно окажется неправильной.
Тебе нужны все правильные способы расставить n пар скобок. Для n = 2 это (()) и ()(). Строка )( неправильная: она закрывает скобку, которую не открывали. (() тоже неправильная: открытых скобок больше, чем закрытых.
Можно построить все строки длины 2n из ( и ) и отобрать правильные. Но для n = 6 это 4096 строк, а правильных среди них только 132. Лучше вообще не строить неправильные.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где нужно построить только правильные строки или разбиения и правило можно проверить на полпути. Проверяй правило перед каждым шагом и обрывай ветку, как только оно нарушено.
Ровно задача урока, open меньше n и close меньше open.
- 1415.The k-th Lexicographical String of All Happy Strings of Length n (откроется в новой вкладке)Средняя
Не добавляй букву, равную последней, строй в порядке a, b, c и остановись на k-й строке.
Отрезай кусок из 1 до 3 цифр и сразу бросай ветку, если он больше 255 или начинается с нуля.
Режь только там, где начало строки палиндром, проверяй двумя указателями и уходи в рекурсию на остаток.