Size of a minimal set of vectors that satisfy an "all subvectors" condition Given some universe $U$, I'd like to know the size of1 a set $S$ of vectors of length $N$ with elements from $U$, such that that given for any list of $M$ indices and corresponding elements, at least one vector in the set has the given elements at the given indices.
Another way of looking at it is the minimum set of vectors which can match a query specified with $M$ elements and $(N-M)$ "don't care" elements in the remaining positions. 
For example, for the 2-element universe $U = \{t, f\}$, $N = 3$ and $M = 2$, the following set of vectors is minimal, I think the minimal set has size 4, satisfied for example with the following vectors:
$\{[t,t,t], [t,f,f], [f,t,f], [f,f,t]\}$
This satisfies any "query" of 2 elements plus 1 don't care, such as $[t, *, t]$ (matches the first element).
This is the same as the minimal set for $N = 2$, since in the case N = M the answer is simply $\left|U\right|^N$.
Certainly this must be a well-known problem, hopefully with a closed-form formula for the minimal size, but the right search terms escape me.

1 Ideally, also a method to generate them (which might fall out naturally from the method to determine the size).
 A: You can formulate this as a set covering problem, with a binary decision variable for each vector in $U^N$ and a linear constraint for each query.
For $U=\{t,f\}$ and $M\in\{2,3,4\}$, I used integer linear programming to obtain the following optimal values for small $N$:
 N M=2 M=3 M=4 M=5
 2   4
 3   4   8
 4   5   8  16
 5   6  10  16  32
 6   6  12  21  32
 7   6  12  24  42
 8   6  12  24
 9   6  12
10   6  12
11   7  12
12   7
13   7

I did not find any relevant sequences in the OEIS.
A: The sets of vectors you describe are called covering arrays, and the minimum covering array size you're interested in is usually denoted $\mathsf{CAN}(t, k, v)$, where in your notation $t = M$, $k = N$, $v = |U|$. It seems that the exact value of $\mathsf{CAN}(t, k, v)$ is only known in a few special/small cases, and in general only asymptotics are known, for example 
$$v^{t-1} \log (k-t+2)(1 + o(1)) \leq \mathsf{CAN}(t, k, v) \leq (t-1)v^t \log k (1 + o(1))$$ (taken from here).
The paper Combinatorial Aspects of Covering Arrays – Charles J. Colbourn has a good overview of the theory (particularly the first two sections), though it's now 15 years old and there have been new results since then. The author also maintains tables of upper bounds on $\mathsf{CAN}(t, k, v)$ for small $t$ and $v$ here.
