The straightforward solution of this problem is to try all possible sets of M cards and check whether they form a Set. This solution is very slow and thus we will not go into details.
A slightly better solution is to try all possible sets of M - 1 cards. For each such a set S, it is clear whether cards in S can form a Set. If so, we can calculate the missing value of each property and thus compute the missing card that will create a Set. Note that such card is uniquely determined. It is enough to check whether it is among the K given cards, and for this, we can use a set or a hashmap.
Note that this solution counts each set M times, once for each missing card.
Both solutions can be improved by cutting the branches of the program in early stages when it is clear that the branch does not lead to a Set. This approach performs reasonably well on many inputs, but its performance is not guaranteed – and its time complexity is always at least linear in the number of Sets.
The sample solution of this problem uses this improvement, and the idea of the meet-in-the-middle approach for M ≥ 4.
We can hash a set of cards to a NM-bit sequence of ones and zeroes that describes for each of the N properties which of the M values are represented in the set.
How can this help us? Suppose that we have two sets of cards C and D, with |C|,|D|≥ 2 and |C| + |D| = M. Do C and D form a Set together? The answer to this question is uniquely determined by their hashes.
For each set C of X = ⌊M∕2⌋ cards that can form a Set we will determine its hash, and construct a hash table where we count the number of times each hash occured.
After the hash table is constructed we take all possible sets of cards of size Y = ⌈M∕2⌉ that can form a Set. For each such set D: From the hash of D we can determine the hash of its matching set C. (The properties that are constant in D must be constant in C as well, with the same value. For the other properties we take the complement of the set of values.) From our hash table we know how many such sets C there are.
As in the previous solution, the resulting number of Sets need to be divided by the number of times we counted each set, which is the number of ways how to choose ⌈M∕2⌉ cards out of M.
(The solution can be made even faster by counting each Set only once. Can you see how to do it?)