Решить методом встречи посередине! [закрыт]

Найти количество подмножеств чья сумма меньше или равна указанного числа К; Ограничения: максимальное число элементов множества n = 40, каждое не должно превышать 10^16 и самое главное: время выполнения работы до 0.5 секунд и использование не больше 20МБ ОЗУ

Пример:
Ввод:
n = 5, s = 1000,
a[n] = { 100, 500, 500, 1500, 1000 }
Вывод:
v = 7 + 1 (пустое подмножество) = { {пустое}, {100}, {500}, {100+500}, {500}, {100+500}, {1000}, {500+500} }

Пытался решить простым перебором сумм всех возможных подмножеств, но при н > 20 время выполнения работы экспоненциально растет.

Если кто может объяснить как работает это метод буду крайне благодарен.

Нашел такое вот объяснение:

1. Split the set of integers into 2 subsets say A and B. A having first n/2 integers and B having rest.
2. Find all possible subset sums of integers in set A and store in an array X. Similarly calculate all possible subset sums of integers in set B and store in array Y. Hence, Size of each of the array X and Y will be at most 2^(n/2).
3. Now merge these 2 subproblems. Find combinations from array X and Y such that their sum is less than or equal to S.
   • One way to do that is simply iterate over all elements of array Y for each element of array X to check the existence of such a combination. This will take O( (2n/2)2) which is equivalent to O(2n).
   • To make it less complex, first sort array Y and then iterate over each element of X and for each element x in X use binary search to find maximum element y in Y such that x + y <= S.
   • Binary search here helps in reducing complexity from 2nto 2n/2log(2n/2)which is equivalent to 2n/2n.
   • Thus our final running time is O(2n/2n).

Не очень понял третий пункт.