Given two subgroups of natural numbers X,Y of the group {1,2,…,100n}

Such that |X| = 3n and |Y| = 7n

Describe an efficient algorithm that finds whether the following exists:

A subgroup of X

B subgroup of Y

Both A,B nonempty s.t |A|=|B|

and the sum of A's elements equals to the sum of B's elements.

At first I thought the solution required building a flow network and searching for a relevant matching.

Later I saw a solution using Dynamic Programming in O(n^4).

Not so efficient…

What is the most efficient way to find the stated algorithm?

Unfold
Noga Alon 2012 Semester A moed A - Matching Subgroups |A|, |B| by student (guest), 28 Jun 2014 13:33