Subset sum на n=40: почему meet-in-the-middle, а не обычное ДП?
Есть n чисел (n ≤ 40), каждое до 10^9. Надо узнать, можно ли набрать подмножество с суммой ровно S (S тоже большое). Обычное subset-sum ДП по сумме не лезет — сумма до 4·10^10, массив dp[S] не выделить. Перебор всех 2^40 тоже не пройдёт. Что делать?