Где применяется
1. Задача
В прошлых уроках рекурсия считала один ответ: размер папки, число Фибоначчи. Бэктрекинг (поиск с возвратом) теми же вызовами функции самой себя обходит все пути и собирает ответ на каждом. На каждом шаге он пробует вариант, идёт глубже, потом отменяет этот выбор и пробует следующий. Новая идея здесь одна: эта отмена, то есть возврат всего к прежнему состоянию перед новой попыткой.
Ты выпускаешь релиз с тремя фичефлагами (переключателями, которые включают и выключают функции программы). Перед выходом CI (система, которая автоматически проверяет код) должен проверить релиз при каждой комбинации флагов: все выключены, включён только первый, включены первый и третий, включены все и так далее. Тебе нужен полный список комбинаций «включено-выключено».
Для трёх флагов комбинаций 8. Для десяти флагов их 1024. Выписывать их руками нереально. Вложенные циклы тоже не подходят: число флагов меняется, и для каждого количества понадобилась бы своя глубина вложенности.
Нужна функция, которая идёт по списку и на каждом элементе пробует оба ответа: оставить элемент снаружи или положить внутрь. Каждый путь от начала до конца даёт одну комбинацию.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитbacktrack([], [1, 2], [])Перечисляем все последовательности длины 2 из [1, 2]. Цикл предлагает каждый вариант на каждом уровне, поэтому значения могут повторяться.
Как узнать
Эти слова в условии значат этот паттерн
- сгенерировать все подмножества/перестановки/комбинации
- n маленькое (примерно n <= 12-20), экспоненциальный перебор допустим
- сделать выбор, уйти в рекурсию, затем отменить выбор перед следующим
- расставить элементы с ограничениями и откатиться при конфликте (N ферзей, судоку)
- вернуть все допустимые варианты, а не один
Похоже, но не то
- Рекурсия (Recursion)
Рекурсия спускается и возвращается. Бэктрекинг ещё и возвращает состояние назад при выходе.
- Рекурсия с мемоизацией (Recursion with memoization)
Кеш окупается, когда аргументы повторяются. На пути из разных выборов это бывает редко.
- Динамическое программирование (1-D) (Dynamic programming (1-D))
Динамика считает или оптимизирует, ничего не перечисляя. Бэктрекинг нужен, когда нужны сами варианты.
- Поиск слова в матрице (DFS/backtracking по сетке) (Matrix word search (grid DFS/backtracking))
Это тот же приём на сетке. Выбор там в том, в какого соседа шагнуть.
Ответ растёт экспоненциально, поэтому n маленькое. Подмножеств из 20 элементов 1e6, перестановок из 10 около 3.6e6.
На LeetCode
Задачи, где нужно перечислить все подмножества или все сочетания выборов, по одному выбору на элемент. На каждом элементе ветвись, уходи в рекурсию и отменяй выбор перед следующей веткой.
Ровно задача урока, пропустить или взять каждое число.
Каждая буква ветвится на строчную и заглавную, а у цифры ветка одна.
Каждая цифра даёт три или четыре ветки вместо двух, а путь равен уже собранному слову.
Сначала отсортируй, а когда пропускаешь значение, пропускай и все его копии, тогда подмножества не повторятся.