Урок

Бэктрекинг

Интуиция: лабиринт с клубком ниток

Представь, что ты в лабиринте и у тебя клубок ниток. На каждой развилке ты выбираешь коридор и идёшь вглубь. Если упёрся в тупик или нашёл выход, ты сматываешь нитку до развилки, то есть отменяешь выбор, и пробуешь следующий коридор. Так ты гарантированно обойдёшь все пути и не заблудишься.

Это и есть бэктрекинг (перебор с возвратом). Вся техника держится на трёх шагах:

Выбрать: добавить элемент в текущее решение.
Углубиться: рекурсивно решать задачу дальше.
Отменить выбор: убрать элемент и вернуться в то же состояние, что было до шага 1.

Бэктрекинг — это обход в глубину (DFS) по дереву решений, которое ты не строишь в памяти. Оно «живёт» в стеке рекурсии.

Дерево решений для подмножеств [1, 2, 3]

Для каждого числа есть два варианта: взять его (левая ветка) или пропустить (правая). На уровне 1 решаем судьбу единицы, на уровне 2 двойки, на уровне 3 тройки. Каждый лист — одно готовое подмножество.

Влево — взять число, вправо — пропустить. 8 листьев = 2³ подмножества. Путь к [1,3]: взять 1, пропустить 2, взять 3

Посмотри на путь к [1,3]. Мы взяли 1 и пошли влево. Потом пропустили 2 и пошли вправо. Потом взяли 3 и снова пошли влево. Когда лист записан в ответ, рекурсия возвращается вверх, и на каждом подъёме мы убираем то, что добавили. Поэтому один и тот же список path честно переиспользуется для всех веток.

Шаблон

Скелет почти всегда один и тот же:

backtrack(состояние):
    если решение готово → сохранить КОПИЮ, return
    для каждого допустимого выбора:
        если выбор заведомо плохой → пропустить (отсечение)
        сделать выбор
        backtrack(новое состояние)
        отменить выбор

Разберём шаблон на своём примере: все двоичные строки длины n без двух единиц подряд. Здесь заодно видно отсечение. Если последняя цифра 1, вторую 1 мы даже не пробуем.

def generate(n):
    res, path = [], []

    def backtrack():
        if len(path) == n:              # решение готово
            res.append("".join(path))   # сохраняем копию
            return
        for ch in "01":
            if ch == "1" and path and path[-1] == "1":
                continue                # отсечение: две единицы подряд
            path.append(ch)             # выбрать
            backtrack()                 # углубиться
            path.pop()                  # отменить выбор

    backtrack()
    return res

Подмножества, перестановки, сочетания

Это три классические формы перебора. Скелет у них общий, отличаются две вещи: какие выборы доступны и когда решение готово.

Задача	Какие выборы доступны	Когда сохранять	Сколько ответов
Подмножества	элементы с индекса `start` и дальше	в каждом узле	2ⁿ
Сочетания из n по k	элементы с индекса `start` и дальше	когда `len(path) == k`	C(n, k)
Перестановки	все ещё не использованные элементы (массив `used`)	когда `len(path) == n`	n!

Главная разница в одной строке:

start означает, что порядок не важен. Мы берём элементы только правее текущего, поэтому [1,2] и [2,1] не появятся дважды.
used[] означает, что порядок важен. Можно взять любой элемент, если он ещё не стоит в path.

Отсечения

Отсечение (pruning) — это проверка до того, как ты полез в ветку: «а может ли здесь вообще получиться ответ?». Если не может, всё поддерево пропускается целиком.

Типичные отсечения:

Нарушено ограничение. Как в нашем примере с двумя единицами подряд.
Сумма уже превысила цель. Если элементы предварительно отсортированы, можно сразу сделать break, потому что дальше числа только больше.
Не хватает элементов. Для сочетаний: если до конца массива осталось меньше элементов, чем нужно добрать до k, дальше идти бессмысленно.
Дубликаты. После сортировки проверка if i > start and nums[i] == nums[i-1]: continue убирает повторяющиеся ветки.

Отсечения не меняют худшую асимптотику, но на практике ускоряют перебор в десятки раз. На собесе их обязательно упоминают.

Сложность

Подмножества: O(n · 2ⁿ). Ответов 2ⁿ, и на копирование каждого уходит до n.
Перестановки: O(n · n!).
Сочетания: O(k · C(n, k)).
Память: O(n) на глубину рекурсии и path, не считая самого ответа.

Это экспоненциальная сложность, и это нормально: ответов столько и есть, быстрее их просто не перечислить. Отсюда практический ориентир: если в условии n ≤ 10–20, это намёк на бэктрекинг.

Как это звучит на собесе

«Задача — перечислить все варианты, значит, бэктрекинг. Строю дерево решений: на каждом шаге выбираю следующий элемент, рекурсивно углубляюсь, потом откатываю выбор. Чтобы не было повторов, передаю индекс start. Отсекаю ветки, где сумма уже больше цели. Сложность O(n · 2ⁿ), потому что ответов экспоненциально много, а память O(n) на стек.»

Частые ошибки

Сохраняешь path, а не его копию. В конце все ответы окажутся одним и тем же пустым списком. Нужно path[:], new ArrayList<>(path) или append([]int(nil), path...) в Go.
Забыл отменить выбор. Без pop() в path копится мусор из соседних веток.
Перепутал start и used. С used в задаче на подмножества получишь лишние повторы, а с start в задаче на перестановки потеряешь часть вариантов.
Отсечение стоит после рекурсивного вызова. Проверять ветку нужно до входа в неё.

Запомни ритм «выбрал → углубился → откатил», и почти любая задача на перебор превращается в заполнение одного и того же шаблона. Дальше закрепим его на практике.