Meet in the middle: встреча посередине для subset sum при n до 40

Коротко

Meet in the middle («встреча посередине») — это не отдельный алгоритм, а приём. Если задача решается полным перебором за $2^n$, а результат можно собрать из двух независимых половин, перебор сокращается до двух переборов по $2^{n/2}$. Разница огромная: при $n = 40$ это $10^{12}$ против двух миллионов.

Задача, на которой всё видно

Дан массив nums из $n \le 40$ целых чисел, возможно отрицательных и по модулю до $10^9$. Нужно посчитать, сколько подмножеств дают в сумме ровно target.

Это классический subset sum, только в версии с подсчётом. Пустое подмножество тоже подмножество, его сумма равна нулю.

nums = [3, 1, 4, 2, 5], target = 6
Подходят: {1, 5}, {4, 2}, {3, 1, 2}  →  ответ 3

Наивное решение: перебор масок

Каждое подмножество кодируется битовой маской из $n$ бит: бит $i$ равен единице, если элемент $i$ взят. Подробнее про маски — в статье про ДП по подмножествам, а перебор подмножеств рекурсией разобран в статье Subsets.

def count_brute(nums, target):
    n = len(nums)
    cnt = 0
    for mask in range(1 << n):
        s = 0
        for i in range(n):
            if mask >> i & 1:
                s += nums[i]
        if s == target:
            cnt += 1
    return cnt


print(count_brute([3, 1, 4, 2, 5], 6))  # 3

Это $O(2^n \cdot n)$. При $n = 20$ около 20 миллионов операций, терпимо даже на Python. При $n = 40$ — $4 \cdot 10^{13}$, то есть часы или дни. Обычный перебор не годится.

А почему не ДП по сумме?

Первая мысль на собеседовании — задача о рюкзаке: dp[s] — число способов набрать сумму s. Для неотрицательных чисел это выглядит так:

def count_dp(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1
    for x in nums:
        for s in range(target, x - 1, -1):
            dp[s] += dp[s - x]
    return dp[target]


print(count_dp([3, 1, 4, 2, 5], 6))  # 3

Сложность $O(n \cdot S)$, где $S$ — диапазон сумм. Если числа до $10^9$, а их 40, сумма может дойти до $4 \cdot 10^{10}$, и массив такой длины не выделить. С отрицательными числами диапазон ещё и удваивается. ДП по сумме — псевдополиномиальный алгоритм: он быстрый, только пока сами числа маленькие.

Отсюда простое правило выбора, к которому вернёмся в конце: маленькие числа — ДП по сумме, маленькое $n$ — встреча посередине.

Идея встречи посередине

Разрежем массив на две половины: L = nums[:n//2] и R = nums[n//2:]. Любое подмножество всего массива однозначно раскладывается на подмножество L и подмножество R, а его сумма — это a + b, где a — сумма левой части, b — сумма правой.

Значит, задача превращается в такую:

1. Выписать все $2^{n/2}$ сумм подмножеств левой половины.
2. Выписать все $2^{n/2}$ сумм подмножеств правой половины.
3. Посчитать пары (a, b), у которых a + b == target.

Третий шаг — это Two Sum в версии с подсчётом пар: для каждой a ищем, сколько раз в правом списке встречается target - a. С хеш-таблицей это одна операция на элемент.

Получается, что мы «идём навстречу» с двух сторон: слева набираем часть суммы, справа — остаток, и встречаемся в хеш-таблице.

Как быстро получить все суммы половины

Можно перебирать маски, как выше, но это лишние $n/2$ на каждую. Удобнее удваивать список: каждый новый элемент либо не берём (старые суммы остаются), либо берём (ко всем старым суммам прибавляем его).

def subset_sums(arr):
    sums = [0]
    for x in arr:
        sums += [s + x for s in sums]
    return sums


print(subset_sums([3, 1]))  # [0, 3, 1, 4]

Каждый шаг удваивает длину, всего выходит $1 + 2 + 4 + \dots + 2^{k-1} = 2^k - 1$ сложений, то есть $O(2^k)$ для половины из $k$ элементов. Дешевле не бывает: столько сумм всё равно придётся выписать.

Полное решение

from collections import Counter


def count_subsets(nums, target):
    half = len(nums) // 2
    left = subset_sums(nums[:half])
    right = Counter(subset_sums(nums[half:]))
    return sum(right[target - s] for s in left)


print(count_subsets([3, 1, 4, 2, 5], 6))  # 3

Counter важен: одна и та же сумма в правой половине может получаться разными подмножествами, и каждое из них — отдельный ответ. Если положить суммы в set, ответ будет занижен.

Разбор на примере

nums = [3, 1, 4, 2, 5], target = 6, half = 2.

Левая половина [3, 1], её суммы: 0, 3, 1, 4.

Правая половина [4, 2, 5], её суммы:

Теперь для каждой левой суммы ищем дополнение до 6:

Итого 3, как и у перебора. Вместо 32 подмножеств мы посмотрели 4 + 8 сумм и 4 поиска в словаре.

Сложность

Пусть $k = n/2$.

• Генерация сумм: $O(2^k)$ для каждой половины.
• Подсчёт через Counter: $O(2^k)$ в среднем.
• Если вместо хеш-таблицы сортировать (это нужно для задач «ближайшая сумма», см. ниже), добавляется $O(2^k \log 2^k) = O(2^k \cdot k)$.

Отсюда стандартная оценка $O(2^{n/2} \cdot n)$. Память — $O(2^{n/2})$: при $n = 40$ это два списка по $2^{20} = 1\,048\,576$ чисел. На Python такой список занимает десятки мегабайт, что обычно укладывается в лимиты.

Для сравнения в числах при $n = 40$:

Цифра «полсекунды» — замер решения из следующего раздела на 40 случайных числах до $10^9$ на обычном ноутбуке. На C++ или Java это будут десятки миллисекунд.

Про то, как вообще читать такие оценки, есть отдельная статья: Big O нотация.

Closest Subsequence Sum: когда точного совпадения нет

Самая популярная задача на эту технику — LeetCode 1755 Closest Subsequence Sum. Дан массив до 40 чисел от $-10^7$ до $10^7$ и goal. Нужно выбрать подмножество, сумма которого ближе всего к goal, и вернуть $|sum - goal|$.

Хеш-таблица тут не поможет: она ищет только точное совпадение. Зато поможет сортировка. Правые суммы сортируем, а для каждой левой суммы a бинарным поиском находим место, куда встала бы goal - a. Ближайший кандидат — один из двух соседей этого места.

from bisect import bisect_left


def min_abs_difference(nums, goal):
    half = len(nums) // 2
    left = subset_sums(nums[:half])
    right = sorted(subset_sums(nums[half:]))
    best = abs(goal)  # пустое подмножество
    for s in left:
        i = bisect_left(right, goal - s)
        if i < len(right):
            best = min(best, abs(s + right[i] - goal))
        if i > 0:
            best = min(best, abs(s + right[i - 1] - goal))
        if best == 0:
            break
    return best


print(min_abs_difference([5, -7, 3, 5], 6))  # 0
print(min_abs_difference([7, -9, 15, -2], -5))  # 1
print(min_abs_difference([1, 2, 3], -7))  # 7

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

Вариант на двух указателях

Если отсортировать обе половины, можно обойтись без бинарного поиска. Левый указатель идёт от самых маленьких сумм, правый — от самых больших. Сумма меньше цели — двигаем левый вперёд, больше — правый назад. Это та же логика, что в Container With Most Water и в статье про два указателя.

def min_abs_two_pointers(nums, goal):
    half = len(nums) // 2
    left = sorted(subset_sums(nums[:half]))
    right = sorted(subset_sums(nums[half:]))
    i, j = 0, len(right) - 1
    best = abs(goal)
    while i < len(left) and j >= 0:
        s = left[i] + right[j]
        best = min(best, abs(s - goal))
        if s < goal:
            i += 1
        elif s > goal:
            j -= 1
        else:
            return 0
    return best


print(min_abs_two_pointers([7, -9, 15, -2], -5))  # 1

Асимптотика та же, $O(2^{n/2} \cdot n)$ из-за сортировок. На собеседовании можно показать любой вариант, главное — объяснить, почему указатели не пропускают ответ: если left[i] + right[j] < goal, то с left[i] любая правая сумма меньше right[j] даст ещё меньше, так что left[i] больше не нужен.

Вариация: максимальная сумма не больше лимита

Та же схема решает «рюкзак без стоимостей» с огромной вместимостью: найти максимальную сумму подмножества, не превышающую limit. Для каждой левой суммы a ищем в отсортированном правом списке наибольшее b <= limit - a через bisect_right(right, limit - a) - 1. Это пригодится в задачах вида «40 предметов с весами до $10^9$, рюкзак вместимостью $10^{12}$».

4Sum II: встреча посередине без подмножеств

LeetCode 454 4Sum II: даны четыре массива a, b, c, d длины $n \le 200$. Нужно посчитать четвёрки индексов, для которых a[i] + b[j] + c[k] + d[l] == 0.

Перебор — $O(n^4)$, при $n = 200$ это $1.6 \cdot 10^9$. Встреча посередине: считаем все суммы пар из a и b в Counter, затем для каждой пары из c и d ищем противоположную сумму.

from collections import Counter


def four_sum_count(a, b, c, d):
    ab = Counter(x + y for x in a for y in b)
    return sum(ab[-(x + y)] for x in c for y in d)


print(four_sum_count([1, 2], [-2, -1], [-1, 2], [0, 2]))  # 2

Время и память $O(n^2)$. Здесь «половины» — это не половины массива, а половины слагаемых: две из четырёх групп слева, две справа. Суть та же: независимые части, перебор каждой и склейка через поиск дополнения.

Не путайте с обычным 4Sum (LeetCode 18), где нужно вернуть уникальные четвёрки из одного массива. Там стандарт — сортировка и два указателя за $O(n^3)$, как в 3Sum с ещё одним внешним циклом. Встреча посередине для 4Sum формально даёт $O(n^2)$ пар, но аккуратно убрать дубликаты и не использовать один индекс дважды заметно сложнее, поэтому на интервью её обычно не ждут.

Где ещё встречается приём

• LeetCode 2035, Partition Array Into Two Arrays to Minimize Sum Difference. $2n$ чисел, $n \le 15$, нужно разбить на две группы по $n$ элементов с минимальной разностью сумм. Встреча посередине плюс группировка левых и правых сумм по количеству взятых элементов: если слева взяли cnt, справа нужно взять n - cnt.
• LeetCode 805, Split Array With Same Average. До 30 чисел, ищем подмножество с тем же средним. Сводится к поиску подмножества фиксированного размера с фиксированной суммой, и встреча посередине — один из рабочих подходов.
• Двунаправленный поиск в графах. BFS одновременно от старта и от финиша: каждый поиск проходит глубину $d/2$, и вместо $b^d$ вершин просматривается порядка $2 \cdot b^{d/2}$. Классика — Word Ladder.
• Криптография. Атака «встреча посередине» объясняет, почему двойное шифрование DES не даёт 112 бит стойкости: перебор ключей с двух сторон превращает $2^{112}$ в порядка $2^{57}$ операций. Поэтому на практике использовали тройной DES.
• Дискретный логарифм. Алгоритм baby-step giant-step для $a^x \equiv b \pmod m$ — тоже встреча посередине: $x = i \cdot k - j$, таблица для одной половины, перебор другой, итого $O(\sqrt{m})$ вместо $O(m)$.

ДП по сумме или встреча посередине

Порог легко оценить в голове. При $n = 40$ встреча посередине стоит порядка $2 \cdot 10^7$ — $4 \cdot 10^7$ операций. ДП дешевле, если $n \cdot S$ меньше этого, то есть при сумме до миллиона. Если в условии $n \le 100$ и числа до 1000 — это ДП. Если $n \le 40$ и числа до $10^9$ — встреча посередине.

Бывают и промежуточные случаи: $n = 60$ с маленькими числами решает только ДП, а $n = 60$ с большими не решает ни то, ни другое (там ищут дополнительную структуру).

Типичные ошибки

1. set вместо Counter при подсчёте. Одна сумма может получаться несколькими подмножествами, а нужно посчитать их все.
2. Забыли пустое подмножество. subset_sums начинается с [0], и это правильно: левое пустое плюс правое непустое — нормальный ответ. Если по условию пустое подмножество не считается, вычтите его отдельно в самом конце (оно даёт сумму 0), а не убирайте 0 из половин.
3. Проверили только одного соседа в бинарном поиске. Для «ближайшей суммы» нужны оба: right[i] и right[i - 1].
4. Разрезали неравномерно. Половины по $n/3$ и $2n/3$ дают $2^{2n/3}$, что при $n = 40$ уже $1.6 \cdot 10^8$. Режьте строго пополам.
5. Генерация сумм через маски с внутренним циклом. Это добавляет множитель $n/2$ и на Python может не пройти по времени. Удвоение списка быстрее.
6. Хранение самих подмножеств. Если нужно вернуть подмножество, а не число, храните рядом с суммой маску (одно число), а не список элементов. Иначе память вырастет в $n/2$ раз.

Как это выглядит на собеседовании

Встреча посередине редко звучит в условии напрямую. Обычно интервьюер даёт задачу, где перебор очевиден, и смотрит, заметите ли вы ограничение $n \le 40$. Хороший ход рассуждений вслух:

1. «Полный перебор — $2^n$, при $n = 40$ это $10^{12}$, не проходит».
2. «ДП по сумме не подходит: числа до $10^9$, таблица не влезет».
3. «Подмножество раскладывается на левую и правую часть независимо. Переберу каждую по $2^{20}$, а склею как Two Sum».
4. «Время $O(2^{n/2} \cdot n)$ из-за сортировки, память $O(2^{n/2})$».

Если задача на точное совпадение — склейка через хеш-таблицу. Если на «ближайшее», «не больше», «минимальная разность» — через сортировку и бинарный поиск или два указателя.

Для тренировки сначала решите Two Sum и 3Sum в тренажёре: шаг склейки во встрече посередине — это ровно они. Потом возьмитесь за 4Sum II и Closest Subsequence Sum на LeetCode, а для сравнения подходов — за Partition Equal Subset Sum (LeetCode 416), где числа маленькие и выигрывает ДП.