Перебор подмножеств (bitmask) на Python: как решать + 6 задач с проверкой

Перебор подмножеств (bitmask) — это приём, когда мы рассматриваем все варианты «какие элементы взять», представляя набор как двоичную маску: i-й бит равен 1, если элемент выбран. В олимпиадных задачах он встречается там, где нужно распределить предметы по группам, проверить все комбинации покупок/лота, подобрать сумму/вес, найти лучшую команду, разложить призы на два сиденья так, чтобы разница была минимальной.

Как распознать задачу

Обычно в условии есть признаки:

• n маленькое (часто до 20–25), но вариантов выбора «очень много»;
• нужно выбрать подмножество или разбить на 2 группы (лево/право, команда A/B);
• есть критерий «минимизировать/максимизировать» (разницу, вес, стоимость) или «существует ли вариант»;
• просят восстановить какой именно набор (индексы), иногда с правилами выбора при равенстве.

Суть приёма

Мы перебираем все маски от 0 до 2^n - 1 и для каждой быстро считаем нужную характеристику (сумму, вес, разницу). Это ускоряет решение, потому что вместо сложных переборов «вручную» мы делаем однотипный цикл по числам и используем быстрые битовые операции и предвычисления.

С чего начать учиться

• Понять связь: маска ↔ список выбранных индексов.
• Научиться проверять/ставить бит: (mask >> i) & 1, mask | (1 << i).
• Тренировать подсчёт суммы по маске и сравнение «лучшего ответа» с аккуратным тай-брейком.
• Запомнить ограничения: 2^n растёт очень быстро; при больших n часто нужен meet-in-the-middle или DP.

Ниже — задачи с автопроверкой и разбором подхода.