The Fewest Sets That Cover Everything
A universe of n items is numbered 1 to n, and m sets of those items are given. Choose as
few of the sets as possible so that every item is in at least one chosen set.
Print the fewest sets needed, or -1 when no choice covers everything.
5 items, sets {1,2,3} {3,4} {4,5} {1,5} -> 2 the first and the third
3 items, sets {1} {2} -> -1 nothing covers item 3
## Why the greedy is not enough
Repeatedly taking the set that covers the most NEW items is the famous greedy for this, and it
is not optimal. The seventh test is the standard shape: sets {1,2,3}, {4,5,6}, {1,4},
{2,5}, {3,6} over six items. The answer is 2, and a greedy that starts by taking any
three-element set and then looks for another is fine here, but change the sizes slightly and it
is not. The table never has to care which.
## The mask is what is COVERED
Every other problem in this topic masks the ITEMS CHOSEN. Here the mask is what has been covered so far, and the sets are the moves:
dp[mask] = the fewest sets whose union is exactly mask, or at least mask
dp[0] = 0
dp[mask | s] = min(dp[mask | s], dp[mask] + 1) for every given set s
The answer is dp[full], or -1 when it is unreachable.
## Why "or at least mask" is harmless
A set may cover items already covered, so mask | s can equal mask. That transition adds 1
and changes nothing, so it never improves anything and can be left in without a guard. If it
were a maximisation rather than a minimisation, the same self-loop would be a bug.
## Why the upward loop still works
Every useful transition moves from mask to mask | s, which is a SUPERSET, so looping
upwards reads only entries already written. The self-loops mentioned above are the only
exception, and they are never improvements.
## Recognising the problem
Minimum set cover is NP-hard in general, so 2^n really is the cost and the constraint on n
is what makes the problem tractable rather than any cleverness in the recurrence. Reading a
small bound on n in a covering problem is itself the hint.
## Boundaries
A single set covering everything answers 1. n singleton sets answer n. An item named by no
set answers -1.
## Cost
Time O(2^n * m). Space O(2^n).