Встреча посередине

В некоторых задачах N примерно равно 40, и перебрать все 2^N подмножеств невозможно. Метод встречи посередине спасает в таких задачах среднего размера. 🤝

Разделите входные данные на две половины. Решите задачу для каждой половины полным перебором, а затем хитро объедините два частичных результата.

Для двух половин размера N/2 требуется по 2^(N/2) вариантов вместо общих 2^N. Такое сокращение до квадратного корня превращает 2^40 в вполне удобные 2^20.

Нужно определить, существует ли подмножество с суммой, равной целевому значению T. Сумма подмножества при N около 40 — учебный пример для метода встречи посередине.

Перечислите все суммы подмножеств из левой половины и сохраните их. При N/2 элементах это всего 2^(N/2) сумм.

Сделайте то же самое для правой половины, построив полный список её сумм подмножеств. Теперь у Вас есть два списка приемлемого размера.

Для каждой правой суммы r нужна левая сумма, равная T минус r. Множество или отсортированный список позволяют быстро выполнить такую проверку.

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

Общий объём работы составляет примерно 2^(N/2), умноженное на логарифмический множитель для поиска или сортировки. Именно эта сложность делает выполнимыми задачи с N около 40.

Вы храните одну половину целиком, поэтому объём памяти растёт до 2^(N/2). Храните только необходимое, чтобы уложиться в ограничение.

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

Вы применяете метод встречи посередине к задаче о подмножестве с N элементами. Какова примерная временная сложность?

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