Hola Gennaro:
Tené en cuenta que para que haya un conjunto de más de n/2 tarjetas equivalentes, tiene que haber un conjunto de más de n/4 tarjetas equivalentes en alguna de las dos mitades. eso te permite reducir el espacio de búsqueda lo suficiente para bajar la complejidad del último paso.
¡saludos!
J