Meet in the middle#11431

Meet in the middle (Editorial)

Divide the input array into two equal parts: $t_{1}, t_{2}, ..., t_{n /2}$ t_1, t_2, ..., t_{n/2} and $t_{n /2 + 1}, t_{n /2 + 2}, ..., t_{n}$ t_{n/2+1}, t_{n/2+2}, ..., t_n. 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^{20}$ 2^{20} 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 $s u m$ 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 - s u m$ 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)$ a = (1, 3, 2),
$b = (2, 1, 4)$ b = (2 ,1, 4)

Iterate over all subsets of the set $a = {1, 3, 2}$ a = \{1, 3, 2\}:

${1} : s u m = 1, m [1] + +$ \{1\}: sum = 1, m[1]++;	${1, 2} : s u m = 3, m [3] + +$ \{1, 2\}: sum = 3, m[3]++;
${3} : s u m = 3, m [3] + +$ \{3\}: sum = 3, m[3]++;	${3, 2} : s u m = 5, m [5] + +$ \{3, 2\}: sum = 5, m[5]++;
${2} : s u m = 2, m [2] + +$ \{2\}: sum = 2, m[2]++;	${1, 3, 2} : s u m = 6, m [6] + +$ \{1, 3, 2\}: sum = 6, m[6]++;
${1, 3} : s u m = 4, m [4] + +$ \{1, 3\}: sum = 4, m[4]++;	${} : s u m = 0, m [0] + +$ \{\}: 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}$ b = \{2, 1, 4\}. In this example, the target sum is $s = 7$ s = 7. For each sum $s u m$ corresponding to a subset of $b$ , add $m [s - s u m]$ m[s - sum] to the final answer.

${2} : s u m = 2, m [7 - 2] = m [5] = 1$ \{2\}: sum = 2, m[7 - 2] = m[5] = 1;
${1} : s u m = 1, m [7 - 1] = m [6] = 1$ \{1\}: sum = 1, m[7 - 1] = m[6] = 1;
${4} : s u m = 4, m [7 - 4] = m [3] = 2$ \{4\}: sum = 4, m[7 - 4] = m[3] = 2;
${2, 1} : s u m = 3, m [7 - 3] = m [4] = 1$ \{2, 1\}: sum = 3, m[7 - 3] = m[4] = 1;
${2, 4} : s u m = 6, m [7 - 6] = m [1] = 1$ \{2, 4\}: sum = 6, m[7 - 6] = m[1] = 1;
${1, 4} : s u m = 5, m [7 - 5] = m [2] = 1$ \{1, 4\}: sum = 5, m[7 - 5] = m[2] = 1;
${2, 1, 4} : s u m = 7, m [7 - 7] = m [0] = 1$ \{2, 1, 4\}: sum = 7, m[7 - 7] = m[0] = 1;
${} : s u m = 0, m [7 - 0] = m [7] = 0$ \{\}: sum = 0, m[7 - 0] = m[7] = 0;

The target sum is $1 + 1 + 2 + 1 + 1 + 1 + 1 + 0 = 8$ 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]);

C++

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 $s u m$ is the sum of the current subset, then increment $m [s u m]$ by $1$ .

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

The variable $i$ contains the bitmask of the current subset of $a$ . The sum of its elements is computed in the variable $s u m$ .

      for (j = 0; j < a.size(); j++)
        if (i & (1 << j)) sum += a[j];

For each obtained sum $s u m$ , increment the value of $m [s u m]$ 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 $r es$ .

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 $s u m$ .

  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 $s u m$ , with all subsets of set a whose sum is $s - s u m$ 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);