# Determine whether two collections of items can be paired

Given collections I (items) and S (slots), where I >= S. And a pairing function that determines whether a slot can accept an item.

Is there an efficient way to find whether a "complete" pairing of items to slots exist, where "complete" means every slot is filled?

(More importantly for my use case... is there a way, other than trying every combination, to determine if no such pairing exists?)

• Hall's Marriage Theorem comes to mind. – Reinstate Monica Aug 24 '18 at 16:02
• @Solomonoff'sSecret It does, but that's a very inefficient test as you have exponentially many sets to check. It's much more efficient to just construct a maximum-cardinality matching and see if it covers everything you need to cover, since that can be done in polynomial time. – David Richerby Aug 24 '18 at 16:03