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

 

Задан массив из n целых чисел. Сколькими способами можно выбрать подмножество, сумма элементов которых равна s?

 

Вход. В первой строке заданы два числа n (1 ≤ n ≤ 40) и s (1 ≤ s ≤ 109) – размер массива и искомая сумма.

Вторая строка содержит n целых чисел t1, t2, ..., tn (1 ≤ ti ​≤ 109) – элементы массива.

 

Выход. Выведите количество способов выбрать подмножество элементов массива, сумма которых равна s.

 

Пример входа 1

Пример выхода 1

4 5

1 2 3 2

3

 

 

Пример входа 2

Пример выхода 2

6 7

1 3 2 2 1 4

8

 

 

РЕШЕНИЕ

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

 

Анализ алгоритма

Разобьем входной массив пополам: t1, t2, ..., tn/2 и tn/2+1, t n/2+2, ..., tn. Первую часть последовательности занесем в массив a, вторую в b.

Решим задачу для последовательности a. Переберем все ее возможные подмножества (таких подмножеств будет не более 220), для каждого подмножества найдем сумму его элементов s и для каждой такой найденной суммы увеличим значение m[s] на 1 (в качестве структуры данных m можно, например, выбрать unordered_map). Таким образом m[s] содержит количество способов выбрать подмножество элементов последовательности a, сумма которых равна s.

Теперь перебираем все подмножества последовательности b. Пусть sum – сумма элементов некоторого такого подмножества. Если это подмножество объединить со всеми возможными подмножествами множества a, сумма которых равна s – sum, то получится подмножество заданного в условии задачи массива, сумма элементов которых равна s.

 

Пример

Рассмотрим второй пример. Разобьем входную последовательность на две:

·        a = (1, 3, 2),

·        b = (2 ,1, 4)

Переберем все подмножества множества а = {1, 3, 2}:

 

{1}: sum = 1, m[1]++;

{1, 2}: sum = 3, m[3]++;

{3}: sum = 3, m[3]++;

{3, 2}: sum = 5, m[5]++;

{2}: sum = 2, m[2]++;

{1, 3, 2}: sum = 6, m[6]++;

{1, 3}: sum = 4, m[4]++;

{}: sum = 0, m[0]++;

 

Структура m содержит следующие значения:

 

Теперь переберем все подмножества множества b = {2, 1, 4}. Искомой суммой в примере является s = 7. Для каждой суммы sum подмножества b будем суммировать значения m[s – sum].

·        {2}: sum = 2, m[7 – 2] = m[5] = 1;

·        {1}: sum = 1, m[7 – 1] = m[6] = 1;

·        {4}: sum = 4, m[7 – 4] = m[3] = 2;

·        {2, 1}: sum = 3, m[7 – 3] = m[4] = 1;

·        {2, 4}: sum = 6, m[7 – 6] = m[1] = 1;

·        {1, 4}: sum = 5, m[7 – 5] = m[2] = 1;

·        {2, 1, 4}: sum = 7, m[7 – 7] = m[0] = 1;

·        {}: sum = 0, m[7 – 0] = m[7] = 0;

Искомая сумма равна 1 + 1 + 2 + 1 + 1 + 1 + 1 + 0 = 8, что и будет ответом.

 

Реализация алгоритма

Объявим рабочие структуры данных.

 

vector<int> a, b;

unordered_map<long long, long long> m;

 

Читаем входные данные. Первую часть последовательности заносим в массив a, вторую в b.

 

scanf("%d %d", &n, &s);

a.resize(n / 2);

for (i = 0; i < n / 2; i++)

  scanf("%d", &a[i]);

 

b.resize(n - n / 2);

for (i = n / 2; i < n; i++)

  scanf("%d", &b[i - n / 2]);

 

Перебираем все подмножества последовательности a и вычисляем суммы их элементов. В структуре unordered_map сохраняем сколько раз среди этих подмножеств встречается каждая сумма. Если sum – сумма текущего подмножества, то m[sum] увеличиваем на 1.

 

for (i = 0; i < (1 << a.size()); i++)

{

  sum = 0;

 

Переменная i содержит битовую маску текущего подмножества а. Сумму элементов этого подмножества вычисляем в переменной sum.

 

      for (j = 0; j < a.size(); j++)

        if (i & (1 << j)) sum += a[j];

   

Для вычисленной суммы подмножества sum увеличиваем m[sum] на 1.

 

  m[sum]++;

}

 

Количество способов составить сумму s из элементов исходного массива подсчитываем в переменной res.

 

res = 0;

 

Перебираем все подмножества последовательности b.

 

for (i = 0; i < (1 << b.size()); i++)

{

  sum = 0;

 

Переменная i содержит битовую маску текущего подмножества b. Сумму элементов этого подмножества вычисляем в переменной sum.

 

  for (j = 0; j < b.size(); j++)

    if (i & (1 << j)) sum += b[j];

 

Если текущее подмножество множества b, сумма элементов которых равна sum, объединить со всеми возможными подмножествами множества a, сумма которых равна s – sum, то получится подмножество заданного в условии задачи массива, сумма элементов которых равна s.

 

  if (m.count(s - sum) > 0) res += m[s - sum];

}

 

Выводим ответ.

 

printf("%lld\n", res);