Comment by spinsser

Why would they need to store the hash for all the combinations?

Why not generate a list of similar passwords to the new password, hash them all using the same salt of the previous password and then compare them.