Где применяется
1. Задача
У тебя три дела: банк, почта, аптека. Ты хочешь перебрать все порядки, в которых их можно обойти. При одних порядках ты успеваешь в банк до закрытия, при других нет. Для трёх дел порядков всего 6, их легко выписать. Для восьми дел их уже 40 320, и в голове столько не удержать.
Нужен способ, который выдаёт каждый возможный порядок набора элементов по одному, ничего не пропуская и ничего не повторяя. Порядок, в котором стоят все элементы, называется перестановкой (permutation). Три элемента дают 6 перестановок, четыре дают 24. Дальше число растёт очень быстро. Его записывают как n! и читают «эн факториал»: для трёх это 3 × 2 × 1, для четырёх 4 × 3 × 2 × 1.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 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
Задачи, где нужно перечислить все порядки набора элементов. Держи флаг used для каждого, добавляй любой неиспользованный, уходи в рекурсию и убирай его обратно.
Задача урока под тем же именем.
Отсортируй и на одном уровне пропускай значение, равное предыдущему неиспользованному, тогда равные значения не меняются местами.
Посчитай буквы, на каждом уровне пробуй каждую букву, у которой ещё остались копии, и считай каждый непустой путь.