Сигнал задачи
Когда применять
Когда полный перебор 2ⁿ уже невозможен, но n достаточно мало, чтобы перечислить примерно 2^(n/2) состояний каждой половины.
Как выбрать подход
- Для проверки существования дополнения подойдут хеш-множество или сортировка одной половины с бинарным поиском.
- Для оптимизации суммы под ограничением удобно отсортировать списки и двигать два указателя либо делать upper_bound для каждого состояния.
- Состояние половины должно сохранять всю информацию, нужную при объединении: сумму, размер, маску или граничное условие.
- Если числовой предел суммы мал, псевдополиномиальное DP по сумме может быть дешевле, чем хранение 2^(n/2) состояний.
Сложность
- Генерация состояний двух половин: O(2^(n/2)) времени и памяти с точностью до постоянного множителя.
- Сортировка одной половины и бинарный поиск для каждого состояния: O(2^(n/2) · n) времени и O(2^(n/2)) памяти.
- После сортировки проход двумя указателями линеен по числу сгенерированных состояний, но сама сортировка остаётся O(2^(n/2) · n).
Границы и ошибки
- Даже 2^(n/2) может не поместиться в память; оценку нужно делать по размеру одного сохранённого состояния, а не только по их числу.
- Пустое подмножество относится к каждой половине и влияет на ответы для нулевой или достижимой одной половиной суммы.
- Удаление одинаковых сумм некорректно, если задача считает число способов или использует разные дополнительные атрибуты.
- Суммы подмножеств могут переполнить тип, даже если каждый отдельный элемент в него помещается.