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);