Smallest set of balls under hamming distance that covers all $n$-bit strings Suppose we defined a set $S = \{x\mid0 \leq x \leq 2^n-1\}$. Notice that all element in $S$ can be represented with a $n$-bit binary string. Now consider subset $S_i$ such that,

$$S_{y_i} = \{y \in S\mid d(y,y_i) \leq t\},$$

where $y_i$ is the $i$th element of $S$ and $d(y_j,y_i)$ is the hamming distance between the binary representation of $y_j$ and $y_i$ and $t &lt; n$.  Obviously, $S_{y_i} \subset S$.

Consider the family ${\Phi = \{S_0, S_1, \ldots, S_{2^n-1}\}}$. Find ${\phi \subset \Phi}$ with smallest cardinality, so that the union of the all elements in $\phi$ is equal to original set $S$ (notice that, each element of $\phi$ is a subset of $S$).

I was not be able to solve. However, I believe it is possible to find $\phi$ with an efficient algorithm rather than using an exhaustive search.

Edit: An example-

Assume $n =3$ and $t = 1$

Then $S = \{0, 1, 2, 3, 4, 5, 6, 7\}$

So, $S_0 = \{y \in S\ |\ d(y,0) \leq 1;\} = \{0, 1, 2, 4\}$

Similarly, $S_1 = \{0, 1, 3, 5\}$; $S_2 = \{0, 2, 3, 6\}$; $S_3 = \{1, 2, 3, 7\}$; $S_4 = \{0, 4, 5, 6\}$; $S_5 = \{1, 4, 5, 7\}$; $S_6 = \{3, 4, 6, 7\}$; $S_7 = \{3, 5, 6, 7\}$;

So, $\Phi = \{S_0, S_1, S_2, S_3, S_4, S_5, S_6, S_7\}$;
Now, for this case the $\phi = \{S_2, S_5\}$ as $S_2 \cup S_5 = S$
The object you are looking for is known as a covering code. Finding the smallest covering code for a given radius is generally a difficult problem, just like its more well-known dual problem, error-correcting codes.