ЕГЭОГЭ
Задания № 24, 27 · ЕГЭ

Решение методом перебора с возвратом

Как строится решение и выполняется возврат при ошибке
2 мин чтенияСложность: Обновлено 29 сентября 2026

Решение методом перебора с возвратом — это последовательный выбор элементов допустимого варианта с отменой последнего выбора, если продолжить построение невозможно или нарушено условие задачи.

Перебор с возвратомАнглийское backtracking означает «движение назад по пройденному пути».
Метод решения задач, при котором алгоритм строит вариант по шагам, проверяет каждый частичный вариант и при ошибке возвращается к предыдущему шагу, чтобы выбрать другой элемент. Такой возврат называют откатом или backtracking. Для работы метода важно хранить состояние перебора: уже выбранные элементы, текущую позицию и доступные продолжения.

Как работает метод

  1. Выбрать очередной элемент или действие.
  2. Проверить, не нарушены ли ограничения.
  3. Если частичный вариант допустим, перейти к следующему шагу.
  4. Если решение построено, сохранить или вывести его.
  5. Если продолжение невозможно, отменить последний выбор и попробовать другой.
\[\text{новое состояние}=\text{предыдущее состояние}+\text{выбор};\qquad\text{возврат}:\ \text{состояние}\leftarrow\text{предыдущее состояние}\]

Частичные варианты образуют дерево: вершина соответствует состоянию, а ветви — возможным выборам. Поэтому метод тесно связан с построением дерева вариантов. Часто перебор записывают как бэктрекинг, обычно с помощью рекурсивной функции.

№
Короткий пример

Нужно составить двузначное число из цифр 1, 2 и 3 без повторений. Сначала выбираем 1, затем 2 и получаем 12. После возврата к выбору второй цифры пробуем 3 и получаем 13. Затем возвращаемся к первой цифре, выбираем 2 и продолжаем построение. Если цифра уже использована, такая ветвь сразу отбрасывается.

!
Не путайте

Возврат с отменой выбора — не то же самое, что обычный перебор всех готовых вариантов. При методе с возвратом проверка выполняется во время построения, поэтому явно невозможные ветви можно не достраивать.

Проверьте понимание

Что нужно сделать, если добавление элемента нарушило условие задачи?

Главное за минуту

Главное

  • Метод строит вариант поэтапно и проверяет ограничения на каждом шаге.
  • При ошибке последний выбор отменяется, после чего пробуется другая ветвь.
  • Возврат позволяет не достраивать заведомо невозможные варианты.