Перебор с возвратом

⏱ 40 мин · 🧩 заданий: 6

Идея: дерево решений

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

[] подмножества [1, 2, 3] / | \ [1] [2] [3] каждый узел — частичное решение / \ | [1,2] [1,3] [2,3] спустились → выбрали элемент | поднялись → отменили выбор (pop) [1,2,3]

Шаблон почти всегда один и тот же:

def backtrack(состояние):
    if решение_готово(состояние):
        result.append(копия(состояние))
        return
    for выбор in варианты(состояние):
        if не_подходит(выбор):        # отсечение
            continue
        сделать(выбор)
        backtrack(состояние)
        отменить(выбор)

Подмножества

def subsets(nums):
    result, path = [], []

    def backtrack(start):
        result.append(path[:])            # копия! path потом изменится
        for i in range(start, len(nums)):
            path.append(nums[i])          # выбрать
            backtrack(i + 1)              # продолжить
            path.pop()                    # отменить

    backtrack(0)
    return result

print(subsets([1, 2, 3]))

Пройдите пример 👣 Пошагово: видно, как path растёт и укорачивается.

Самая частая ошибка — забыть копию

result.append(path) добавит ссылку на один и тот же список. После всех pop() он станет пустым, и в результате окажутся одни пустые списки. Нужно path[:] или list(path).

result, path = [], []
for x in [1, 2]:
    path.append(x)
    result.append(path)        # ошибка: одна и та же ссылка
print(result)
path.clear()
print(result)

Перестановки

def permutations(nums):
    result, path, used = [], [], [False] * len(nums)

    def backtrack():
        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)
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result

print(permutations([1, 2, 3]))

Сочетания и отсечения

Выбрать k элементов из n: отличие от подмножеств — сохраняем только пути длины k. Отсечение: если элементов осталось меньше, чем нужно добрать, дальше идти бессмысленно.

calls = 0

def combine(n, k, prune):
    global calls
    result, path = [], []

    def backtrack(start):
        global calls
        calls += 1
        if len(path) == k:
            result.append(path[:])
            return
        need = k - len(path)
        stop = n - need + 2 if prune else n + 1     # не начинаем, если не хватит элементов
        for i in range(start, stop):
            path.append(i)
            backtrack(i + 1)
            path.pop()

    backtrack(1)
    return result

for prune in (False, True):
    calls = 0
    r = combine(12, 9, prune)
    print(f"отсечение={prune}: сочетаний {len(r)}, вызовов {calls}")

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

Ферзи

Классика: расставить n ферзей на доске n×n, чтобы они не били друг друга. Ставим по одному ферзю в строку и помним занятые столбцы и диагонали.

def solve_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    placement, solutions = [], []

    def backtrack(row):
        if row == n:
            solutions.append(placement[:])
            return
        for col in range(n):
            if col in cols or row - col in diag1 or row + col in diag2:
                continue
            cols.add(col); diag1.add(row - col); diag2.add(row + col)
            placement.append(col)
            backtrack(row + 1)
            placement.pop()
            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

    backtrack(0)
    return solutions

solutions = solve_queens(6)
print(f"решений для 6×6: {len(solutions)}")
for col in solutions[0]:
    print(" ".join("Q" if c == col else "." for c in range(6)))
print([len(solve_queens(n)) for n in range(1, 9)])

Готовые генераторы itertools

Если нужно просто перечислить варианты, а не перебирать с отсечениями, используйте itertools — это быстрее и короче.

from itertools import permutations, combinations, combinations_with_replacement, product

print(list(permutations("abc", 2)))
print(list(combinations([1, 2, 3, 4], 2)))
print(list(combinations_with_replacement("ab", 2)))
print(["".join(p) for p in product("01", repeat=3)])

На собеседовании обычно просят написать перебор руками, а itertools упомянуть как «в продакшене я бы взял готовое».

Сложность и когда это не перебор

Задача	Число вариантов
подмножества	2ⁿ
перестановки	n!
сочетания из n по k	C(n, k)
скобки из n пар	число Каталана, ≈ 4ⁿ / n^1.5

Это экспоненты, так что перебор годится для n до 10–20. Если в задаче просят количество способов или оптимум (а не все варианты), а подзадачи повторяются — это сигнал к динамическому программированию из следующего урока.

Сигналы задачи на перебор

«Найдите все варианты/комбинации/перестановки», «расставьте», «можно ли составить», маленькие ограничения (n ≤ 15), головоломки (судоку, ферзи, слово в сетке).

Итог

Шаблон: выбрать → рекурсивно продолжить → отменить выбор.
Добавляйте в результат копию текущего пути.
Отсечения отбрасывают заведомо бесполезные ветки и ускоряют перебор в разы.
Сложность экспоненциальная; для «сколько способов» и «оптимум» думайте о ДП.

Войдите, чтобы отмечать пройденные уроки.

	2ⁿ вариантов	n! вариантов	C(n, k) вариантов
`permutations(xs)`
`combinations(xs, k)`
`product([0, 1], repeat=n)`