It turns out storing hashed combinations is barely any stronger than plaintext.

The attacker just has to be successful against one of the combinations (eg characters 1+2+3), which doesn't offer enough combinations to make it a sufficient slow guess even if the password is randomly-chosen; for real user-chosen passwords it falls very quickly. Once the attacker has that it's trivial to leverage to guess other combinations (eg 1+2+4) repeatedly until you have the whole password.

If you have to implement a n-of-m password system, you can't do one-way hashing, so you have to fall back to keeping it encrypted in the database, and keeping the encryption keys separate and more strongly protected (eg in an HSM).

(But yes: n-of-m is generally a bad idea for usability as well as of very doubtful security benefit.)