Перебор с возвратом на Python: как решать + 3 задачи с проверкой

Перебор с возвратом (backtracking) — это приём, когда вы строите ответ по частям: выбрали первый элемент, затем второй, и так далее, а если упёрлись в запрет, откатываетесь и пробуете другой вариант. В олимпиадных задачах так решают распределения и расстановки: назначить каждому персонажу квест, собрать пати по правилам, поставить роботов на позиции, выбрать порядок действий с ограничениями.

Как распознать backtracking по условию:

• нужно составить объект из нескольких решений: «для каждого i выбрать одно», «расставить N предметов», «построить строку/последовательность»;
• есть жёсткие ограничения на совместимость (таблица 0/1, запрет повторов, конфликтующие пары);
• просят найти хотя бы один вариант, посчитать варианты, или выдать минимальный (например, лексикографически минимальный);
• N небольшой (часто до 20–30, а иногда фиксирован, как 5), но «в лоб» N! или 2^N всё равно много без отсечений.

Суть приёма: держим текущее частичное решение и множество уже использованных элементов, добавляем следующий выбор и сразу проверяем локальные запреты. Если продолжать нельзя — возвращаемся на шаг назад. Это ускоряет решение, потому что вы не перебираете заведомо невозможные продолжения и можете остановиться сразу, как только нашли первый подходящий ответ в правильном порядке (для лексикографического минимума — перебирать кандидатов по возрастанию).

С чего начать учиться:

• научиться писать рекурсивную функцию «поставить позицию k» и делать откат изменений;
• продумать состояние: что уже выбрано (массив ответа), что занято (used), какие проверки нужны;
• выбрать порядок перебора (по возрастанию для минимальности; иногда выгодно начинать с самых ограниченных позиций);
• добавить отсечения: проверять ограничения сразу при добавлении, не откладывая на конец;
• тренироваться на задачах «найти любой», затем «минимальный», затем «посчитать все».

Ниже — задачи с автопроверкой и разбором подхода к перебору с возвратом.