Representemos el conjunto de mujeres ya escogidas con una máscara de bits, donde 0 significa que está libre y 1 que no, y denotemos ~dp_{mask}~ como la cantidad de formas de conseguir matchear las mujeres marcadas en ~mask~ con la cantidad correspondiente de los primeros hombres, ahora veamos las transiciones, cuando se vaya a intentar matchear el ~x~-ésimo hombre, se prueban todos los conjuntos de ~x - 1~ mujeres, y a cada uno de ellos se le prueba añadir cualquier mujer libre que sea compatible con el hombre ~x~, o sea para cada ~mask~ con ~x - 1~ bits encendidos se le sumará ~dp_{mask}~ a ~dp_{mask|(1<<k)}~ tal que ~k~ es una mujer libre compatible con el hombre ~x~.

Complejidad ~O(2^n\cdot{n})~