Рекурсия и backtracking: подмножества

Backtracking — это систематический перебор всех вариантов с откатом неудачных.

Backtracking (перебор с возвратом) — построение решения по шагам: выбираем вариант, рекурсивно продолжаем, затем откатываем выбор и пробуем другой.

Дерево решений

Для каждого элемента есть выбор: взять его в подмножество или нет. Эти бинарные выборы образуют дерево из 2^n листьев — все возможные подмножества. Backtracking обходит это дерево.

def subsets(nums):
    result = []
    current = []

    def backtrack(start):
        result.append(current[:])   # копия текущего набора
        for i in range(start, len(nums)):
            current.append(nums[i])  # выбираем
            backtrack(i + 1)         # идём дальше
            current.pop()            # откатываем

    backtrack(0)
    return result

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

Вывод:

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

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

Похожий приём для всех перестановок: на каждом шаге берём ещё не использованный элемент.

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

    def backtrack():
        if len(current) == len(nums):
            result.append(current[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            current.append(nums[i])
            backtrack()
            current.pop()
            used[i] = False

    backtrack()
    return result

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

Вывод:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

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

Ключевая пара — выбор и откат: current.append(...) перед рекурсией и current.pop() после. Откат возвращает состояние к тому, каким оно было до выбора, чтобы испробовать следующую ветку «с чистого листа». Важна копия current[:] при сохранении ответа: current — один и тот же список, и без копии все ответы окажутся одинаковыми (пустыми) в конце. Параметр start в подмножествах не даёт генерировать дубликаты типа [1,2] и [2,1].

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

• Сохранять current без копии — все элементы результата будут ссылаться на один список.
• Забыть откат pop() — состояние «протечёт» в соседние ветки.
• Не передавать start в подмножествах — получите дубликаты и комбинации в разном порядке.

Итог

• Backtracking перебирает дерево решений: выбор → рекурсия → откат.
• Подмножества — 2^n вариантов, перестановки — n! вариантов.
• Сохраняйте копию текущего состояния и всегда откатывайте выбор.