--- title: "Бэктрекинг: шаблон из трёх строк, код на Python и разбор N ферзей" url: https://algopath.pro/ru/blog/bektreking language: ru summary: "Перебор с откатом для задач «все перестановки», «все подмножества» и «N ферзей». Шаблон, код на Python, разбор на примере, отличие от DP и типичные ошибки." updated: 2026-10-17 --- # Бэктрекинг: шаблон из трёх строк, код на Python и разбор N ферзей **Короткий ответ.** Бэктрекинг это перебор с откатом. Мы строим решение по шагам, и как только шаг ведёт в тупик, отменяем его и пробуем другой. Так решают задачи «все перестановки», «все подмножества», «расставить ферзей», «судоку». Ниже шаблон, код на Python, разбор на примере и типичные ошибки. ## Что такое бэктрекинг? Есть частичное решение. На каждом шаге выбираем следующий элемент из допустимых. Если выбор ведёт к полному решению, записываем его. Если выбор ведёт в тупик, откатываем и берём следующий. Это обход дерева вариантов в глубину. Узел это частичное решение, ребро это один выбор. Листья это полные решения или тупики. Слово «откат» описывает главный жест. Сделали шаг, вернулись, сделали другой. Состояние после возврата ровно такое же, как до шага. Отличие от простого перебора: тупики обрезаются рано. Если первые два ферзя бьют друг друга, остальные шесть не расставляем. ## По каким словам в задаче узнать бэктрекинг? - «Все перестановки», «все подмножества», «все сочетания». - «Все способы разбить строку», «все пути в лабиринте». - «Расставить N ферзей», «решить судоку». - «Найти хотя бы одно решение при ограничениях», где n меньше 20. Общий признак: нужен список всех ответов или ответ при жёстких ограничениях, и n маленькое. Если просят только число ответов, чаще подходит динамическое программирование. ## Как устроен шаблон бэктрекинга? - Функция принимает текущее частичное решение path. - Если path полное, записываем копию и выходим. - Для каждого допустимого варианта: добавляем его в path, вызываем функцию, убираем обратно. Три строки «добавить, вызвать, убрать» это и есть откат. Без третьей строки path растёт без остановки. Обрезка тупиков живёт в проверке допустимости варианта перед первой строкой. ## Как это выглядит на примере? Перестановки [1, 2, 3]. path пустой. Берём 1: path [1]. Берём 2: path [1, 2]. Берём 3: path [1, 2, 3], полное, записали. Убираем 3, вариантов нет. Убираем 2. Теперь берём 3: path [1, 3]. Берём 2: [1, 3, 2], записали. Откат до пустого. Берём 2 первым: [2, 1, 3], [2, 3, 1]. Потом [3, 1, 2], [3, 2, 1]. Шесть ответов, ни один не пропущен. ## Как написать бэктрекинг на Python? ``` def permutations(nums): result, path, used = [], [], [False] * len(nums) def go(): if len(path) == len(nums): result.append(path[:]) # копия, а не ссылка return for i, x in enumerate(nums): if used[i]: continue used[i] = True path.append(x) go() path.pop() # откат used[i] = False go() return result def subsets(nums): result, path = [], [] def go(start): result.append(path[:]) for i in range(start, len(nums)): path.append(nums[i]) go(i + 1) path.pop() go(0) return result ``` Параметр start в subsets запрещает возвращаться назад. Так [1, 2] и [2, 1] не считаются дважды. ## Чем бэктрекинг отличается от соседних приёмов? | Приём | Что даёт | Размер n | Пример | | --- | --- | --- | --- | | Бэктрекинг | Все решения или одно при ограничениях | До 15-20 | N ферзей, перестановки | | Динамическое программирование | Число решений или оптимум | До тысяч | Число путей, рюкзак | | Обход в глубину | Достижимость, компоненты | До миллионов | Острова в сетке | | Жадный алгоритм | Оптимум без перебора | Любой | Задача о выборе заявок | ## Как решить N ферзей? Ставим по одному ферзю в каждую строку. Для строки r перебираем столбцы c. Столбец занят или диагональ занята, пропускаем. Держим три множества: занятые столбцы, диагонали r - c и диагонали r + c. Проверка занятости стоит O(1). Дошли до строки n, записали расстановку. Для n = 8 полный перебор дал бы 8 в восьмой степени вариантов. Обрезка тупиков оставляет несколько тысяч. ## Как решить Combination Sum? Даны числа и цель. Нужны все наборы, где числа в сумме дают цель. Число можно брать много раз. Идём по кандидатам с индекса start. Берём число, вычитаем из цели, вызываем себя с тем же start. Цель стала нулём, записываем путь. Цель ушла в минус, откатываем. Сортировка кандидатов позволяет обрывать цикл, когда число больше остатка. ## На каких ошибках ломается бэктрекинг? - Записывают path вместо path[:]. Все ответы становятся одним пустым списком. - Забывают откат после рекурсивного вызова. - Проверяют ограничение только в конце вместо каждого шага. Обрезка не работает. - Не сортируют вход в задачах с дубликатами, и одинаковые ответы повторяются. ## Как объяснить приём на собеседовании? Скажите: нужны все решения, n маленькое, строю ответ по шагам с откатом. Назовите три строки шаблона. Назовите, где обрезаете тупики. Сложность честно называйте экспоненциальной: O(n!) для перестановок, O(2ⁿ) для подмножеств. Потом скажите, что обрезка сильно уменьшает реальное число шагов. Отработать узнавание приёма можно на странице [бэктрекинг](/ru/patterns/backtracking). Соседний приём разобран на странице [рекурсия](/ru/patterns/recursion). ## Вопросы и ответы ### Чем бэктрекинг отличается от обхода в глубину? Механика одна. Разница в том, что бэктрекинг строит решение и отменяет шаг. Обход в глубину просто помечает вершины посещёнными. ### Как убрать дубликаты в подмножествах с повторами? Отсортируйте вход. В цикле пропускайте элемент, если он равен предыдущему и предыдущий не взят на этом уровне. ### Где приём встречается в реальных системах? В решателях ограничений: составление расписаний, раскладка задач по машинам. В парсерах с откатом, где грамматика допускает несколько разборов. В играх, когда движок перебирает ходы на несколько шагов вперёд. ### Когда бэктрекинг слишком медленный? Когда n больше 20 и нет сильной обрезки. Тогда ищите динамическое программирование или жадный подход.