A festival has n duties numbered 0 .. n-1. Each crew in crews can only be hired as a whole
and then takes over all the duties in its list. A rota is a set of crews such that every
duty is taken by exactly one hired crew: no duty is left out and no duty is double booked.
Return the number of different rotas. Crews are told apart by their position in crews, so two
crews with the same duty list count as different choices. When n = 0 the empty rota is the one
valid rota.
Examples
Input: n = 4, crews = [[0, 1], [2, 3], [0, 2], [1, 3], [0, 1, 2, 3], [1, 2]]
Output: 3
Explanation: {[0, 1], [2, 3]}, {[0, 2], [1, 3]} and {[0, 1, 2, 3]}.
Input: n = 3, crews = [[0], [1, 2], [0, 1], [2]]
Output: 2
Input: n = 3, crews = [[0, 1], [1, 2]]
Output: 0
Constraints
0 <= n <= 40,0 <= len(crews) <= 200- every crew is a non-empty list of distinct duties from
0 .. n-1 - the answer can be very large (Python integers do not overflow)
Goals
- Branch on the duty with the fewest usable crews instead of on the crews themselves
- Memoise on the set of covered duties to count huge numbers of rotas