11431. Meet in the middle

 

An array of n integers is given. In how many ways can you choose a subset of its elements such that their sum is equal to s?

 

Input. The first line contains two integers: n (1 ≤ n ≤ 40) – the size of the array, and s (1 ≤ s ≤ 109) – the required sum.

The second line contains n integers: t1, t2, ..., tn (1 ≤ ti ​≤ 109) – the elements of the array.

 

Output. Print a single integer – the number of ways to choose a subset of the array elements whose sum is equal to s.

 

Sample input 1

Sample output 1

4 5

1 2 3 2

3

 

 

Sample input 2

Sample output 2

6 7

1 3 2 2 1 4

8

 

 

SOLUTION

meet in the middle

 

Algorithm analysis

Divide the input array into two equal parts: t1, t2, ..., tn/2 and tn/2+1, t n/2+2, ..., tn. Store the first part in array a and the second in array b.

First, solve the problem for sequence a. Iterate over all possible subsets of a (there will be at most 2²⁰ of them). For each subset, calculate the sum of its elements s, and increment the value m[s] by 1. As the data structure m, we can use, for example, an unordered_map. Thus, m[s] will contain the number of ways to choose a subset from array a whose elements sum to s.

Then, iterate over all subsets of array b. Let sum be the sum of elements in one such subset. If we combine this subset with all subsets of array a whose sum is equal to s – sum, the result will be a subset of the original array whose elements sum to s.

 

Example

Let's consider the second example. Divide the input sequence into two parts:

·        a = (1, 3, 2),

·        b = (2 ,1, 4)

Iterate over all subsets of the set à = {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]++;

 

The structure m will contain the following values after processing:

 

 

Now, iterate over all subsets of the set b = {2, 1, 4}. In this example, the target sum is s = 7. For each sum sum corresponding to a subset of b, add m[s – sum] to the final answer.

·        {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;

The target sum is 1 + 1 + 2 + 1 + 1 + 1 + 1 + 0 = 8, which is the final answer.

 

Algorithm implementation

Declare the data structures.

 

vector<int> a, b;

unordered_map<long long, long long> m;

 

Read the input data. Store the first half of the sequence in array a, and the second half in array 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]);

 

Iterate over all subsets of sequence a and compute the sum of their elements. In the unordered_map structure, keep track of how many times each sum occurs among these subsets. If sum is the sum of the current subset, then increment m[sum] by 1.

 

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

{

  sum = 0;

 

The variable i contains the bitmask of the current subset of à. The sum of its elements is computed in the variable sum.

 

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

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

   

For each obtained sum sum, increment the value of m[sum] by 1.

 

  m[sum]++;

}

 

The number of ways to obtain the sum s from the elements of the original array is counted in the variable res.

 

res = 0;

 

Iterate over all subsets of sequence b.

 

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

{

  sum = 0;

 

The variable i contains the bitmask of the current subset of b. The sum of the elements in this subset is computed in the variable sum.

 

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

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

 

If we combine the current subset of set b, whose sum of elements is sum, with all subsets of set a whose sum is s – sum, the result will be a subset of the original array whose sum of elements is equal to s.

 

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

}

 

Print the answer.

 

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