Rather than testing every possible combination of things, all pairs simplifies the exercise to testing every pair of things which reduces the complexity significantly, for example instead of 700,000 possible combinations, all pairs would be about 500 combinations.

While this reduces the number of tests, does it help find bugs?  All pairs works because when things break, they have a tendency to break because of the faulty interaction of two things rather than 3 or more.   A long term study of medical device failures found a strong correlation for this.   For all the failures reported, a quarter of them would have been found with all pairs testing.  The true result is probably much better than this, because a lot of the failure reports did not have enough detail to allow proper analysis.  Of the detailed reports, 98% of the failures would have been found with all pairs testing!  The paper, "Failure Modes in Medical Devices", is at csrc.ncsi.nist.gov/staff/kuhn/final-rqse.pdf

 If you do all pairs testing, you could still use minimal pairs to get better test effectivess.  By starting your tests with all the minimal pairs first, this would give a good broad coverage of combinations.  The remaining all pairs combinations could then be used to finish the exercise.