5.1 Генерация подмножеств¶

В этом разделе мы рассмотрим задачу перебора всех подмножеств некоторого множества из n элементов. Это один из самых базовых приёмов полного перебора: если нужно проверить все возможные наборы элементов, то сначала надо уметь эти наборы порождать.

Например, если дано множество {0, 1, 2}, то его подмножества таковы:

∅, {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}.

Нетрудно заметить, что у множества из n элементов ровно 2^n подмножеств. Это сразу подсказывает и сложность любого полного перебора по подмножествам: обычно она не может быть лучше, чем O(2^n), потому что сами варианты уже нужно хотя бы один раз перечислить.

Обычно используют два основных подхода:

рекурсивный перебор;
перебор по битовой маске.

Оба метода очень важны и регулярно встречаются в олимпиадном программировании.

Способ 1. Рекурсивный перебор¶

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

не включать его в текущее подмножество;
включать его в текущее подмножество.

То есть для каждого элемента у нас есть ровно два варианта. Именно поэтому общее число вариантов равно 2^n.

Ниже приведена стандартная идея на C++:

void search(int k) {
    if (k == n) {
        // обработать подмножество
    } else {
        search(k+1);
        subset.push_back(k);
        search(k+1);
        subset.pop_back();
    }
}

Здесь:

k — номер текущего элемента;
subset — вектор, в котором хранится текущее строящееся подмножество;
n — количество элементов во множестве {0,1,...,n-1}.

Запуск начинается с вызова:

search(0);

Как работает эта рекурсия¶

Когда вызывается search(k), функция решает судьбу элемента k:

сначала она рассматривает вариант, где элемент k не берётся;
затем добавляет k в subset, рассматривает вариант, где он берётся, и после этого удаляет его обратно.

Когда k == n, это означает, что решения для всех элементов уже приняты. Следовательно, текущее содержимое subset — готовое подмножество, которое можно вывести, проверить или использовать в вычислениях.

Небольшой пример¶

Пусть n = 3, то есть мы перебираем подмножества множества {0,1,2}.

Тогда дерево решений выглядит так:

элемент 0: взять или не взять;
элемент 1: взять или не взять;
элемент 2: взять или не взять.

flowchart TD
    A["start: []"]
    A --> B["не брать 0"]

    B --> C["не брать 1"]
    C --> D["не брать 2 → {}"]
    C --> E["взять 2 → {2}"]

    B --> F["взять 1 → {1}"]
    F --> G["не брать 2 → {1}"]
    F --> H["взять 2 → {1,2}"]

Hold "Ctrl" to enable pan & zoom

flowchart TD
    A["start: []"]
    A --> B["взять 0 → {0}"]

    B --> C["не брать 1 → {0}"]
    C --> D["не брать 2 → {0}"]
    C --> E["взять 2 → {0,2}"]

    B --> F["взять 1 → {0,1}"]
    F --> G["не брать 2 → {0,1}"]
    F --> H["взять 2 → {0,1,2}"]

Hold "Ctrl" to enable pan & zoom

В результате получаются такие варианты:

∅
{2}
{1}
{1,2}
{0}
{0,2}
{0,1}
{0,1,2}

То есть рекурсия фактически строит двоичное дерево, где на каждом уровне мы решаем, включать ли очередной элемент.

Почему этот способ удобен¶

Главное достоинство рекурсии — её наглядность. Очень легко добавить дополнительную логику:

посчитать сумму элементов текущего подмножества;
проверить, удовлетворяет ли оно условию;
остановить поиск раньше времени, если текущее состояние уже бесполезно.

Именно поэтому рекурсивный подход часто служит основой для более сложных методов, например для backtracking.

Способ 2. Перебор по битовой маске¶

Другой очень популярный подход основан на двоичной записи числа.

Каждое подмножество множества из n элементов можно закодировать строкой из n битов:

1 означает, что элемент включён;
0 означает, что элемент не включён.

Например, если у нас 5 элементов, то маска

11001

может означать подмножество {0,3,4}.

Обычно договорённость такая:

последний бит соответствует элементу 0;
предпоследний — элементу 1;
и так далее.

То есть битовая маска — это просто число от 0 до 2^n - 1, и перебрать все подмножества можно обычным циклом.

Базовый код¶

for (int b = 0; b < (1<<n); b++) {
    // обработать подмножество
}

Здесь b — битовая маска текущего подмножества.

Например, если n = 3, то цикл переберёт значения от 0 до 7:

000 → ∅
001 → {0}
010 → {1}
011 → {0,1}
100 → {2}
101 → {0,2}
110 → {1,2}
111 → {0,1,2}

Как извлечь элементы из маски¶

Если нужно получить сами элементы подмножества, можно пройтись по всем битам и проверить, какие из них равны единице:

for (int b = 0; b < (1<<n); b++) {
    vector<int> subset;
    for (int i = 0; i < n; i++) {
        if (b & (1<<i)) subset.push_back(i);
    }
}

Условие

b & (1<<i)

проверяет, включён ли элемент i в подмножество.

Пример¶

Пусть n = 4, а текущая маска равна 13.

В двоичном виде:

13 = 1101

Это значит:

бит 0 равен 1 → элемент 0 входит;
бит 1 равен 0 → элемент 1 не входит;
бит 2 равен 1 → элемент 2 входит;
бит 3 равен 1 → элемент 3 входит.

Следовательно, маска 13 задаёт подмножество {0,2,3}.

Сравнение двух подходов¶

Оба способа перебирают все 2^n подмножеств, но удобны в разных ситуациях.

Рекурсия удобнее, когда:¶

нужно строить решение постепенно;
хочется легко добавлять отсечения;
важна понятная логика перебора.

Битовые маски удобнее, когда:¶

нужно компактно хранить подмножество;
надо быстро проверять принадлежность элемента;
подмножества участвуют в динамике, битовых операциях или мемоизации.

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

Полезные замечания¶

1. Сложность перебора¶

Всего подмножеств 2^n, поэтому:

если n = 20, то это примерно миллион вариантов — обычно допустимо;
если n = 25, вариантов уже больше 33 миллионов — это может быть тяжело;
если n = 40, полный перебор подмножеств уже почти всегда слишком медленный.

Поэтому генерация подмножеств чаще всего применяется при сравнительно небольших n.

2. Необязательно хранить всё подмножество¶

Во многих задачах не нужно явно складывать элементы в vector<int>. Иногда достаточно прямо во время перебора:

считать сумму;
считать количество элементов;
обновлять лучший ответ.

Это позволяет сделать решение компактнее и быстрее.

3. Маски особенно полезны в динамическом программировании¶

Позже битовые маски часто используются в задачах вида:

«какие элементы уже выбраны»;
«какие вершины уже посещены»;
«какие объекты входят в текущее состояние».

То есть подмножество хранится не как контейнер, а как одно целое число.

Итог¶

Задача генерации подмножеств — одна из базовых тем полного перебора.

Есть два классических способа:

рекурсивный перебор — понятный и гибкий;
битовые маски — компактные и очень удобные для оптимизаций.

Именно с этих техник начинается множество задач на полный перебор, перебор состояний и динамическое программирование по подмножествам.

Если у множества n элементов, то нужно помнить главное:

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

Эти идеи постоянно встречаются в олимпиадных задачах, поэтому их стоит довести до автоматизма.