I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm does). The only solution I have is to recursively enumerate all the possible matchings, discarding the recursive branches which do not satisfy the conditions. This algorithm has a complexity of O(n!), with n being the number of items in each set.
I found this similar question that shows that the upper bound to the number of solutions is exponential. Is there any better algorithm than the one I have so far?
In the context of similar questions, this paper by Gusfield comes up. However, it solves a different problem.