Где применяется
1. Задача
Тебе нужно поставить на дежурство 2 человек из группы в 4. Ты хочешь перечислить все возможные пары, чтобы сравнить их. Пара {Аня, Боря} здесь то же самое, что {Боря, Аня}: на дежурстве те же двое. Порядок ничего не значит.
Если взять перебор порядков из прошлого урока, ты получишь {Аня, Боря} и {Боря, Аня} как два разных результата, и потом придётся убирать повторы. Для пар это мелочь. Для выбора 5 человек из 30 каждая группа появится 120 раз: перебор выдаст 17 100 720 порядков ради 142 506 разных групп. Выбор, где порядок не важен, называется сочетанием (combination). Каждое сочетание можно перечислить ровно один раз, без чистки повторов.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- сгенерировать все подмножества/перестановки/комбинации
- 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
Задачи на выбор групп, где порядок не важен, часто с заданной суммой. Передавай вниз индекс start, тогда каждая группа собирается только в одном порядке.
Задача урока под тем же именем.
Выбирай k чисел от 1 до 9 через start и обрывай ветку, как только сумма превысила цель.
Уходи в рекурсию с тем же start, а не start плюс один, потому что число можно брать повторно.
Отсортируй, бери каждое число один раз и пропускай значение, равное предыдущему на том же уровне.