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. asked 04 Jul '17, 12:43

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. Cheers! answered 26 Sep '17, 11:19

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. answered 04 Jul '17, 12:53

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.
answered 04 Jul '17, 14:51

Would this algorithm run efficiently for large inputs (10^10)? answered 12 Jan, 14:49
