I was at realestate.com.au when they started writing microservices in 2013 and we were all facing this exact issue. Out of that experience, the (now open source) contract testing tool called "Pact" was written (I am now one of the maintainers). I wrote a blog about the combinatorial explosion problem here many years ago now! https://www.rea-group.com/blog/enter-the-pact-matrix-or-how-...
From the Pact docs: 'Contract testing is a technique for testing an integration point by checking each application in isolation to ensure the messages it sends or receives conform to a shared understanding that is documented in a "contract".' By focussing just on the messages we get tests which are fast, give us quick feedback, and scale linearly instead of combinatorially.
Some good resources are:
https://pact.io (for information about contract testing and the Pact tool itself)
https://pactflow.io/how-pact-works/ (explains how Pact works)
https://docs.pact.io/faq/convinceme (answers the question of why you would want to do contract testing)
https://slack.pact.io (a friendly 1000+ member community which is very experienced dealing with these kinds of issues)
https://docs.pact.io/pact_broker/can_i_deploy (addresses how we handle and channel this combinatorial explosion for good instead of evil!)