Перейти к содержанию

5.5 Метод meet in the middle

Meet in the middle — это приём, при котором пространство поиска делят на две части примерно одинакового размера. Для каждой части выполняют отдельный перебор, а затем результаты этих переборов эффективно объединяют.

Этот метод особенно полезен тогда, когда полный перебор всех вариантов слишком дорог. Если удаётся быстро «склеить» ответы из левой и правой половин, то вместо одного огромного перебора можно выполнить два заметно меньших. На практике это часто позволяет заменить сложность порядка 2^n на 2^(n/2), что даёт огромный выигрыш.

Идея на интуитивном уровне

Представим, что у нас есть набор из n элементов, и мы хотим перебрать все подмножества. Полный перебор требует пройти по всем 2^n вариантам. Но если разбить набор на две половины, то:

  • у первой половины будет около 2^(n/2) подмножеств;
  • у второй половины тоже будет около 2^(n/2) подмножеств.

Дальше мы отдельно считаем информацию для каждой половины, а потом ищем, какие пары результатов вместе дают нужный ответ.

Именно в этом и состоит смысл метода: не пытаться решить задачу целиком сразу, а сначала решить её для двух половин и потом объединить решения.

Пример задачи

Дан список из n чисел и число x. Нужно определить, можно ли выбрать некоторые числа из списка так, чтобы их сумма была равна x.

Например, пусть дан список:

[3, 6, 7, 11]

Если x = 20, ответ да, потому что можно выбрать числа 3, 6 и 11, и их сумма равна 20.

Если же x = 10, ответ нет, потому что никакое подмножество элементов списка не даёт сумму 10.

Прямой полный перебор

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

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

Для маленьких n это допустимо, но при росте n такой перебор очень быстро становится слишком медленным.

Как помогает meet in the middle

Разобьём исходный список на две части:

  • A — первая половина чисел;
  • B — вторая половина чисел.

Пусть каждая часть содержит примерно n/2 элементов.

Теперь:

  1. Переберём все подмножества множества A и сохраним их суммы в список SA.
  2. Переберём все подмножества множества B и сохраним их суммы в список SB.
  3. После этого проверим, существуют ли такие суммы a из SA и b из SB, что

a + b = x.

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

Почему это верно? Потому что любое подмножество исходного множества естественным образом раскладывается на:

  • часть элементов, взятых из A;
  • часть элементов, взятых из B.

Следовательно, сумма любого подмножества исходного набора равна сумме некоторого подмножества A и некоторого подмножества B.

Подробный пример

Пусть дан список:

[3, 6, 7, 11]

и требуется получить сумму x = 20.

Разделим список пополам:

  • A = [3, 6]
  • B = [7, 11]

Шаг 1. Суммы подмножеств первой половины

Подмножества множества A:

  • ∅ → сумма 0
  • {3} → сумма 3
  • {6} → сумма 6
  • {3, 6} → сумма 9

Значит,

SA = [0, 3, 6, 9]

Шаг 2. Суммы подмножеств второй половины

Подмножества множества B:

  • ∅ → сумма 0
  • {7} → сумма 7
  • {11} → сумма 11
  • {7, 11} → сумма 18

Значит,

SB = [0, 7, 11, 18]

Шаг 3. Ищем пару сумм

Теперь нужно понять, есть ли числа a из SA и b из SB, для которых

a + b = 20.

Замечаем, что:

  • 9 принадлежит SA
  • 11 принадлежит SB
  • 9 + 11 = 20

Значит, ответ да.

Какому выбору элементов это соответствует?

  • сумма 9 в SA получена подмножеством {3, 6};
  • сумма 11 в SB получена подмножеством {11}.

Итак, искомое подмножество исходного списка — это {3, 6, 11}.

Почему это быстрее

Если в каждой половине примерно n/2 элементов, то количество подмножеств в каждой половине равно 2^(n/2).

Значит:

  • генерация SA занимает O(2^(n/2));
  • генерация SB занимает O(2^(n/2)).

После этого остаётся эффективно проверить, можно ли взять сумму из SA и сумму из SB, которые в сумме дадут x.

Если списки отсортированы, это можно сделать быстро — например, бинарным поиском или двумя указателями.

В результате получаем алгоритм порядка O(2^(n/2)) с точностью до логарифмических множителей при сортировке.

Это намного лучше, чем O(2^n).

Важно понимать, что:

2^(n/2) = sqrt(2^n)

То есть мы уменьшаем размер перебора не «немного», а коренным образом.

Как реализовать идею на практике

Один из удобных способов выглядит так:

  1. Разделить массив на две части.
  2. Сгенерировать все суммы подмножеств левой части.
  3. Сгенерировать все суммы подмножеств правой части.
  4. Отсортировать один или оба списка.
  5. Для каждой суммы s из первого списка искать, есть ли во втором списке сумма x - s.
flowchart TD
    A["Массив чисел a"] --> B["Разделить на две части:<br/>A и B"]

    B --> C["Построить все суммы подмножеств<br/>для A → S_A"]
    B --> D["Построить все суммы подмножеств<br/>для B → S_B"]

    C --> E["Отсортировать S_A"]
    D --> F["Отсортировать S_B"]

    E --> G["Искать пару сумм:<br/>x + y = target"]
    F --> G

    G --> H["Если пара найдена — ответ YES"]
    G --> I["Если пары нет — ответ NO"]
Hold "Ctrl" to enable pan & zoom

Если хотя бы одно такое значение найдено, задача решена.

Небольшой набросок на C++

vector<long long> sums(vector<int> a) {
    vector<long long> res;
    int m = a.size();
    for (int mask = 0; mask < (1 << m); mask++) {
        long long s = 0;
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) s += a[i];
        }
        res.push_back(s);
    }
    return res;
}

bool possible_sum(vector<int> v, long long x) {
    int n = v.size();
    vector<int> a(v.begin(), v.begin() + n / 2);
    vector<int> b(v.begin() + n / 2, v.end());

    vector<long long> sa = sums(a);
    vector<long long> sb = sums(b);

    sort(sb.begin(), sb.end());

    for (long long s : sa) {
        if (binary_search(sb.begin(), sb.end(), x - s)) {
            return true;
        }
    }
    return false;
}

Этот код:

  • строит все суммы подмножеств для обеих половин;
  • сортирует суммы второй половины;
  • для каждой суммы из первой половины ищет дополнение до x.

Где метод особенно полезен

Метод meet in the middle часто применяют в задачах, где:

  • полный перебор по 2^n уже слишком медленный;
  • n ещё недостаточно велико для чисто полиномиального решения;
  • ответ можно собрать из двух независимых частей;
  • удобно работать с суммами, масками или другими агрегированными характеристиками половин.

Типичные примеры:

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

Запомните

  • Полный перебор всех вариантов часто даёт сложность 2^n.
  • Если разбить задачу на две половины, можно перебрать каждую отдельно.
  • Для каждой половины сохраняют «сжатую информацию» обо всех вариантах — например, суммы подмножеств.
  • Затем результаты двух половин объединяют.
  • Во многих задачах это позволяет заменить перебор 2^n на перебор порядка 2^(n/2).

Метод meet in the middle — один из самых полезных приёмов для задач, где обычный полный перебор уже почти подходит, но всё ещё слишком медленный. Именно в таких ситуациях он часто превращает нерешаемую задачу в вполне практическую.