подсчитать все подмножества целых чисел (включая отрицательные), сумма которых равна x

Question

Мне дан массив максимальной длины 40, содержащий целые числа в [-10 ^ 9; 10 ^ 9]. Мне также дается ожидаемая сумма X, которая лежит в [0; 10 ^ 9]. Теперь я должен передать общее количество подмножеств этой суммы X. Я не могу придумать способ справиться с отрицательными числами. Сначала я попробовал метод грубой силы, который отлично работает для небольших входных массивов, но непригоден для больших:

auto r = 0ULL;
for(auto i = 0ULL; i < (1ULL << n) - 1ULL; ++i) {
    auto x = 0ULL;
    for(auto j = 0ULL; j < n; ++j) {
        if(i & (1ULL << j)) {
            x += values[j];
        }
    }
    r += x == sum;
}
cout << r << '\n';

Затем я попытался запомнить промежуточные результаты добавлений, чтобы мне не приходилось их вычислять более одного раза для тех же элементов. Но это занимает ОЧЕНЬ много места (должно быть около 9 ТБ для входов длиной 40 x)). Может кто-нибудь подскажет, как лучше?

Answer 1

Диапазон сумм и количество элементов выглядят слишком большими для динамического c программирования из-за недостатка памяти.

Но ограничение в 40 элементов позволяет применить что-то вроде принцип «встречи посередине» .

Разделите первые 20 элементов и подсчитайте суммы для всех возможных подмножества - просто пройдите через 2 ^ 20 подмножеств (включая пустой!) (используя рекурсию или двоичное представление номера подмножества или каким-либо другим способом) и запишите суммы на карту, содержащую пары (sum, count).

Проделайте то же самое для второй половины. Обратите внимание, что размер карт достаточно надежен.

Пройдитесь по первым ключам карты и найдите соответствующие ключи на второй карте. Псевдокод:

for sum in map1:
    if map2.contains(X - sum):
        result += map1[sum] * map2[X - sum]

Answer 2

Подсказка: вы можете использовать повторение. Пусть num_subsets[i][k] будет количеством подмножеств values[0], values[1], ..., values[i], которые в сумме могут составлять k. Тогда

num_subsets[i][k] = num_subsets[i - 1][k – values[i]] + num_subsets[i - 1][k]

Тогда num_subsets[n-1][x] - ваш ответ.