How to most efficiently store possible combinations of categories? I have a table of categories (currently with 14 rows, not likely to change). A need to cache combinations of categories emerged, so I'm creating a table of allowed combinations (only few hundreds of the ~10^10 combinations are likely to be ever searched for and I can constraint it even more). However, I'm not sure how to implement it.

Combination of 14 columns for each row in the category table looks simple, but it doesn't feel right. Any change in the category data would make a change in the combination table structure necessary.

Another option was to make the combination only with ID and combination name and store the important information in the category_combination join table. This feels "right", but making sure that each combination is unique becomes a non-trivial task (unlike simple applying unique constraint over a group of columns in the former case). In PostgreSQL, I would make a deferred trigger, but this is not possible in MySQL. The best option I can think of with MySQL is to make it a function and then calling it from the client app; if it finds a dupe, I'd cancel the transaction. I would aggregate the categories in the combination with GROUP_CONCAT (ordered, of course), either in the query or in an auxiliary view, and then compare the arrays.

Still, I'm not sure if there's no more elegant way, either a completely different approach, or an optimization of the second approach. How to do it best?

EDIT: category combinations will be often used in search, so it needs to be optimized for searching. Adding new a combination will be rare and I hope we will avoid adding new categories, though this should still be possible (even with a lot of work).
How about the SET datatype.  With that, you could represent all combinations of 14 categories in 14 bits (2 bytes).