Equal sum partition

general
,
1

Equal partition: Given a set A of 40 real numbers, find out if there is any way to split A in two sets such that the sums of their elements are equal. (Hint: complexity O(2n/2))

How do I solve this problem using meet in the middle? I found it on this blog.

2

don’t you understand this explanation?

We already know that the 2 subsets we are looking for have the same sum which is equal to the sum of all the elements in the set / 2, so we only need to find the elements of 1 of the 2 subsets. A neat solution would be splitting the set into 2 random disjoint subsets of size N / 2, namely A and B. Then we insert each sum of every combination of elements from A into a hash table. We then check the sums of every combination of elements from B i. e. for a sum K, if S / 2 - K is in the hash, then we have a solution. Final complexity: O(2 ^ (N / 2 + 1)). An alternative to this solution would be a well implemented algorithm which randomly moves elements from one subset to the other. This outperforms the 2 ^ (N / 2) algorithm on memory and may even have better results on time.

3

For anyone else trying to understand it, we are trying to reduce the problem to find a single set of elements whose sum is equal to S/2 where S is sum of all elements in the array.

  1. So we divide set of size N(=40) into two halves(=2*20) A and B.
  2. Find all possible sums for A array(T = 2^20) and store it in a hash-table.
  3. Generate sum of elements from array B and at every step check for a sum K in B array, is there a sum = S/2 - K in the hash-table.
  4. If it’s there you have your solution. So the first subset will be a collection of all the elements from array A forming sum = S/2 - K and elements from array B (forming sum=K) such that the sum is now S/2 of the complete subset and the second subset has all other elements not included in the first subset.
4

This problem requires you to divide and conquer. The set of 40 real numbers must be broken to two smaller sets of 20, and merged efficiently.
One clever algorithm to do this is Meet in the Middle. A hint for this is you are looking for an aggregate function on the two sets (sum), hence MitM is a possibility.

Here is a video editorial I made on Meet in the Middle!

Cheers!

2 Likes
5

Would this algorithm run efficiently for large inputs (10^10)?

6

I went through it before but I couldn’t understand. Though I get it now.