How many subsets of $\{0,1,2,3,4,5,6,7,8,9\}$ could be realized as the set of distinct digits of a prime?
Possible solution
Obviously, the empty subset is not realizable.
Five singleton subsets are certainly realizable, namely $\{1\}$ (corresponding to the repunit primes like $11$), $\{2\}, \{3\}, \{5\},$ and $\{7\}$.
For the subsets $S$ with at least two elements, two conditions must be met for $S$ to be realizable: $S \cap \{1,3,7,9\} \ne \emptyset$ and $\gcd(S)=1$.
The number of subsets of $\{0,1,2,3,4,5,6,7,8,9\}$ disjoint from $\{1,3,7,9\}$ is $2^6=64$, so the number of subsets that are not disjoint from $\{1,3,7,9\}$ is $2^{10}-2^6=1024-64=960$. Of those $960$ subsets, four of them are singletons, which have already been covered above, leaving only $956$. Of the $956$ remaining subsets, $\{0,7\}$ has a gcd of $7$, leaving only $955$. Finally, of the $955$ remaining subsets, $2^4-2^2-2=16-4-2=10$ of them (all non-singleton subsets of $\{0,3,6,9\}$ that are not disjoint from $\{3,9\}$) contain only multiples of $3$, leaving only $945$ subsets with a gcd of $1$.
So, the answer must be at most $5+945=950$. But is it exactly $950$?
Yes, but I don't see a better way to solve this than brute force. In fact, for more than half of the remaining subsets $D \subset \{0, \ldots, 9\}$ we can find an example with $|D|$ digits, i.e., that uses each digit in $D$ exactly once, and we can find an example with $\leq |D| + 1$ digits for every remaining subset but one.
Call a number whose digits are pairwise distinct a permutation of its digit set $D$; per the question statement we prohibit numbers with leading zeros. Notice that if there is no prime permutation of $D$ if $3 \mid \sum_{d \in D} d$, since in (exactly) those cases all of the permutations are themselves divisible by $3$. A quick script shows that of the $625$ remaining elements, all but $19$ admit permutations that are primes; writing a set $\{d_1, \ldots, d_k\}$ of digits as $[d_1 \ldots d_k]$, we have $$\begin{array}{rr} \hline D & \textrm{prime} \\ \hline [13] & 13 \\ [14] & 41 \\ \vdots\,\,\,& \vdots\,\, \\ [013456789] & 103456789 \\ [023456789] & 203457869 \\ \hline \end{array}$$
The $19$ exceptions are the sets $$\begin{array}{rl} \hline |D| & D \\ \hline 2 & [01], [49] \\ 3 & [023], [029], [034], [038], [047], [148], \\ & \qquad [158], [178], [247], [259], [469], [689] \\ 4 & [0146], [0257], [0469], [0478], [0569] \\ \hline \end{array}$$ (No exception has $|D| > 4$.) For example, all $18$ permutations of $[0146]$ are composite; the four permutations that are odd numbers are: $$4061 = 31 \cdot 131, \qquad 4601 = 43 \cdot 107, \qquad 6041 = 7 \cdot 863, \qquad 6401 = 37 \cdot 173 .$$
But except for $[259]$ all of these exceptions admit primes of length $|D| + 1$: $$\begin{array}{rr} \hline D & \textrm{prime} \\ \hline [01] & 101 \\ [49] & 449 \\ \vdots\,\,\, & \vdots\,\, \\ [0478] & 40087 \\ [0569] & 50069 \\ \hline \end{array}$$
if there were a number with digit set $[259]$ of length $4$, its digits would be $(2,5,9,9)$ is some order---otherwise the number would be divisible by $3$---but all $6$ numbers with those digits and coprime to $10$ (that is, ending in $9$) are composite: \begin{multline} 2599 = 23 \cdot 111, \qquad 2959 = 11 \cdot 269, \qquad 5299 = 7 \cdot 757, \\ 5929 = 7^2 \cdot 11^2, \qquad 9259 = 47 \cdot 197, \qquad 9529 = 13 \cdot 733 . \end{multline}
On the other hand, $25999$ is prime, so the length of a minimal example for $\{2, 5, 9\}$ is $5 = |\{2, 5, 9\}| + 2$. This observation completes the case that $3 \not\mid \sum_{d \in D} d$.
We saw above that if $3 \mid \sum_{d \in D} d$, then a minimal example must have at least $|D| + 1$ digits. Again a naive script finds that in fact all of the remaining sets $D$ admit such a prime, e.g.,
$$\begin{array}{rr} \hline D & \textrm{prime} \\ \hline [12] & 211 \\ [15] & 151 \\ \vdots\,\,\, & \vdots\,\, \\ [123456789] & 1123465789 \\ [0123456789] & 10123457689 \\ \hline \end{array}$$