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

Шаблон: выбрать, исследовать, отменить

Дерево решений для подмножеств трёх элементов: на каждом уровне взять или пропустить
Дерево решений для подмножеств трёх элементов: на каждом уровне взять или пропустить

Храним один изменяемый path. На каждом шаге:

  1. выбрать: добавить элемент в path;
  2. исследовать: рекурсивно решить оставшуюся часть;
  3. отменить: убрать элемент, чтобы следующий выбор начался с чистого состояния.

Когда path готов, сохраняем его копию (path[:]), потому что тот же список продолжит меняться.

Подмножества: 2^n листьев

Для каждого элемента две ветки: пропустить или взять. У множества из n элементов 2^n подмножеств.

python
def subsets(items):
    result, path = [], []

    def explore(i):
        if i == len(items):
            result.append(path[:])
            return
        explore(i + 1)           # branch 1: skip items[i]
        path.append(items[i])    # choose
        explore(i + 1)           # branch 2: take items[i]
        path.pop()               # undo