XOR и маски подмножеств

У XOR есть два особенно полезных свойства: x ^ x = 0 и x ^ 0 = x. А битовая маска набора превращает выбор «взять/не взять» в число, где каждый бит отвечает за один индекс. Обе техники короткие, но зависят от очень строгих условий.

Когда пары исчезают, а выборы кодируются маской

Первая задача: в массиве каждое число встречается ровно два раза, кроме одного; найти одиночное. Вторая: для массива из не более 20 чисел посчитать, сколько подмножеств имеет сумму не больше лимита. В обеих задачах порядок элементов не важен, но причины решений разные.

Что честно перебирают все подмножества

Для одиночного числа можно для каждого элемента считать его частоту — O(n^2), или использовать hash map O(n) памяти. Для подмножеств полный перебор уже является решением: существует 2^n возможных масок, и каждую нужно оценить. Главное — честно увидеть предел n, а не скрывать экспоненту.

Где частоты и списки подмножеств тратят лишнее

В первой задаче повторный подсчёт частот не нужен: пары можно взаимно уничтожить XOR. В задаче подмножеств нельзя избежать проверки всех вариантов в общем случае, но можно не строить списки подмножеств и держать выбор компактно в битах.

Почему XOR сокращает пары, а биты выбирают индексы

XOR коммутативен и ассоциативен, поэтому все парные значения исчезают независимо от порядка, а аккумулятор оставляет одиночное. Для маски mask бит i равен 1 тогда и только тогда, когда values[i] выбрано. Маски от 0 до (1 << n) - 1 покрывают каждое подмножество ровно один раз.

Что накоплено после очередного элемента и бита

После обработки первых i чисел xorValue равен XOR этого префикса; все завершившиеся пары в нём сократились. Во внутреннем цикле маски sum равна сумме элементов, чьи уже просмотренные биты равны 1. Нельзя трактовать один и тот же бит как два разных индекса.

Как пройти пары и все маленькие подмножества

1. Для одиночного числа начать xorValue = 0 и сделать XOR со всеми значениями.
2. Для подмножеств проверить ограничение n.
3. Перебрать целые маски от 0 до 2^n - 1.
4. Для каждого индекса добавить значение, если установлен соответствующий бит; сравнить сумму с лимитом.

Как явно ограничить экспоненциальный перебор

Обе программы содержат две маленькие функции, потому что урок учит двум разным применениям одного двоичного представления. Ограничение n <= 20 делает 2^n осознанным учебным выбором, а не скрытой проблемой производительности. В C++ каждый элемент имеет тип int, но сумма и лимит — long long: сумма не более 20 значений int гарантированно помещается в этот тип.

C++17

#include <cassert>
#include <iostream>
#include <stdexcept>
#include <vector>

using namespace std;

int singleAmongPairs(const vector<int>& values) {
    int xorValue = 0;
    for (int value : values) xorValue ^= value;
    return xorValue;
}

int countSubsetsAtMost(const vector<int>& values, long long limit) {
    if (values.size() > 20) throw invalid_argument("n is too large for subset enumeration");
    int count = 0;
    int allMasks = 1 << values.size();

    for (int mask = 0; mask < allMasks; ++mask) {
        long long sum = 0;
        for (size_t index = 0; index < values.size(); ++index) {
            if ((mask & (1 << index)) != 0) sum += values[index];
        }
        if (sum <= limit) ++count;
    }
    return count;
}

int main() {
    assert(singleAmongPairs({4, 1, 2, 1, 2}) == 4);
    assert(countSubsetsAtMost({1, 2, 3}, 3) == 5);
    assert(countSubsetsAtMost({2'000'000'000, 2'000'000'000}, 2'000'000'000LL) == 3);
    cout << singleAmongPairs({7, 3, 7}) << '\n';
}

Python 3

def single_among_pairs(values: list[int]) -> int:
    xor_value = 0
    for value in values:
        xor_value ^= value
    return xor_value


def count_subsets_at_most(values: list[int], limit: int) -> int:
    if len(values) > 20:
        raise ValueError("n is too large for subset enumeration")

    count = 0
    for mask in range(1 << len(values)):
        total = 0
        for index, value in enumerate(values):
            if mask & (1 << index):
                total += value
        if total <= limit:
            count += 1
    return count


assert single_among_pairs([4, 1, 2, 1, 2]) == 4
assert count_subsets_at_most([1, 2, 3], 3) == 5
print(single_among_pairs([7, 3, 7]))

Где появляется множитель 2 в степени n

Одиночное число: O(n) времени и O(1) дополнительной памяти. Это верно только если остальные значения встречаются ровно два раза. Перебор масок: O(n * 2^n) времени и O(1) дополнительной памяти помимо входа; при n=20 это примерно миллион масок, при n=40 — уже около триллиона.

Какие кратности и размеры нарушают контракт

Один элемент сразу остаётся XOR-ответом. Три одинаковых числа не удовлетворяют контракту «все пары плюс одно». Пустая маска всегда существует и имеет сумму 0; она считается, если лимит не меньше 0. В C++ сдвиг 1 << values.size() безопасен здесь только из-за ограничения n <= 20.

Какие пары и маски проверяют решение

• [4,1,2,1,2] -> 4;
• один элемент;
• проверить, что нарушение кратности пар не имеет обещанной интерпретации;
• для [1,2,3], limit 3 перечислить пять масок: {}, {1}, {2}, {3}, {1,2};
• limit меньше 0 и пустой массив;
• отказ при n > 20.

Когда отмена пар отличается от счётчика

XOR: «все элементы встречаются дважды, кроме одного», отмена пар, чётность присутствия. Маски: n мал (обычно до 20–25), каждая сущность либо выбрана, либо нет, и нужно перебрать/проверить все комбинации.

Когда XOR и полный перебор дают ложную уверенность

XOR не находит уникальный элемент, если другие числа встречаются три раза или частоты неизвестны; тогда нужна другая побитовая логика или счётчик. Не перебирайте маски при n=50 только потому, что выражение выглядит коротким: экспонента не станет быстрой. При отрицательных значениях подмножеств нельзя преждевременно отсекать по сумме без дополнительного доказательства.

Самопроверка независимости XOR от порядка

Вопрос: почему порядок [1,2,1,4,2] не меняет XOR-ответ?
Ответ: XOR ассоциативен и коммутативен; пары 1^1 и 2^2 обнуляются в любом порядке, остаётся 4.

Самопроверка двоичного выбора индексов

Вопрос: какая маска кодирует подмножество с индексами 0 и 2 из четырёх элементов?
Ответ: 0101₂ (число 5): биты 0 и 2 установлены, биты 1 и 3 — нет.

Потренируйте чтение маски подмножества

Для массива [3,4,5,6] найдите подмножество с суммой ровно 9, перечисляя маски. Записывайте не только сумму, но и двоичную маску. Затем объясните, почему добавление пятого элемента вдвое увеличивает число проверяемых масок.

Самостоятельный перебор малого набора

Не используйте подсказки: сначала назовите реальный предел n и объясните, почему он допустим.

Задача 1

Дан набор не более 20 чисел. Посчитайте подмножества, у которых сумма делится на 3, и верните одну маску с максимальной суммой среди таких подмножеств.

Что короткие битовые операции требуют от входа

XOR решает задачу только благодаря точной кратности пар, а маска честно перечисляет все выборы малого набора. В обоих случаях короткая операция опирается на сильный контракт входа.