Knowledge required: meet-in-the-middle

Anyone with knowledge of the subset sum problem probably recognized this problem immediately. For anyone who does not know, the subset sum problem is one of the most famous NP-complete problems, you can learn more about it here.

If we add all samples to one array, with the antimatter samples being negative, the problem is reduced to finding the number of subsets that sum to ~0~. The naive ~\mathcal{O}((N+M) \times 2^{N+M})~ solution involves iterating over all possible subsets using bitmasks. For full points, we use a technique called meet-in-the-middle. Similar to divide and conquer, we divide the array into ~2~ equally sized arrays. In the first half, we use the same naive technique to find all subset sums and cache them. For each subset sum ~S~ in the second half, we look for the number of occurrences of ~-S~ in the cached results. This can be done by using either binary search or a map.

Time Complexity: ~\mathcal{O}\left(\frac{N+M}{2} \times \sqrt{2^{N+M}}\right)~

Bonus: Can you solve this problem using meet-in-the-middle?