Note that any solution will be of the form $S=\{0,1,s_2,\cdots,s_j,n-1,n\}$ and then $S'=\{0,1,n-s_j,\cdots,n-s_2,n-s_1,n-1,n\}$ is also a solution. If $S=S'$ one might call it a symmetric solution. This requires that $n$ and/or $m(n)$ is even. In any case it might be pleasant to try to maximize $|S \cap S'|.$ A possible alternate, or further, goal would be to minimize the number of distinct jumps between successive entries.Aside from aesthetics, when there are several optimal solutions, the ones with the must symmetry or regularity might be fruitful for suggesting generalizations.
In a somewhat trivial sense, for any two solutions $S_1,S_2$ of size $m(n),$ One can change $S_1$ to $S_2$ by shifting entries. So it is hard to say if one solution is essentially different from another.
Many values of $n$ (but not all) seem to have optimal solutions with this structure:
>Start with $0,1,2,\cdots, d-1=s_d$ end with $s_{d+p+1}=n-(d-1),\cdots, n-2,n-1,n$ and in the middle put entries $s_{d+1},s_{d+2},\cdots,s_{d+p}$ which satisfy $s_{i+1}-s_i \leq d$ for $d-1\leq i \leq d+p.$
This will always give a solution of size $2d+p$. For an optimal solution $d$ should be around $\sqrt{\frac{n}2}$ and $p$ as small as possible given $n,d,$ so $p=\lceil \frac{n+2}d-3\rceil.$ In some cases there are $3$ values of $d$ which work.
---
$m(23)=12$ and one solution is $S=\{0,1,3,5,6,13,15,16,18,20,22,23\}$
There are $22$ symmetric solutions. The lower halves are
$ \left\{ 0,1,2,3,4,9 \right\} , \left\{ 0,1,2,3,6,10 \right\} ,
\left\{ 0,1,2,3,7,10 \right\} , \left\{ 0,1,2,3,7,11 \right\} ,
\mathbf{\left\{ 0,1,2,4,5,11 \right\}} , \left\{ 0,1,2,4,6,9 \right\} ,
\left\{ 0,1,2,4,7,10 \right\} , \left\{ 0,1,2,5,6,8 \right\} ,
\left\{ 0,1,2,5,7,10 \right\} , \left\{ 0,1,2,5,8,10 \right\} ,
\left\{ 0,1,2,5,8,11 \right\} , \mathbf{\left\{ 0,1,3,4,5,11 \right\} ,
\left\{ 0,1,3,4,6,11 \right\} , \left\{ 0,1,3,4,7,9 \right\} ,
\left\{ 0,1,3,4,8,9 \right\} , \left\{ 0,1,3,4,8,10 \right\} ,
\left\{ 0,1,3,4,9,10 \right\} , \left\{ 0,1,3,4,9,11 \right\} ,
\left\{ 0,1,3,5,6,8 \right\} , \left\{ 0,1,3,5,6,10 \right\} ,
\left\{ 0,1,3,5,6,11 \right\} , \left\{ 0,1,3,5,7,8 \right\}} $
The values of $d$ represented are $3,4,5.$ The ones in bold merit further perusal. They do not fully fit the scheme described as there are jumps greater than the relevant $d$.
---
$m(20)=10$ and the given solution $S=\{0,1,3,4,9,11,16,17,19,20\}$ is symmetric.
There are no solutions which fit the scheme above as $$6+\lceil \frac{22}3 \rceil-3=8+\lceil \frac{22}4 \rceil-3=11.$$
---
$m(38)=15$ and the solution $$S=\{0,1,2,3,4,9,14,19,24,29,31,34,35,37,38\}$$ can be shifted to give this solution
with $d=4$
$$S=\{0, 1, 2, 3, 7, 11, 15, 19, 23, 27, 31, 35, 36, 37, 38\}$$
and also this one with $d=5$
$$\{0, 1, 2, 3, 4, 9, 14, 19, 24, 29, 34, 35, 36, 37, 38\}.$$
In those cases there is no choice for the middle entries as $\frac{40}{4}-3=7$ and $\frac{40}5-3=5.$
---
For $n=2d^2-2$ there are optimal symmetric solutions with $|S|=4d-3$. These are the ones listed by Rob Pratt for $n=6,16.$
- $\{0,1,2,3,7,11,15,19,23,27,28,29,30\}$ works for $d=4.$
- $\{0,1,2,3,4,9,14,19,24,29,34,39,44,45,46,47,48\}$ works for $d=5.$
One last example: $m(43)=16$ and one solution is $$S=\{0, 1, 3, 4, 5, 8, 14, 20, 26, 29, 35, 38, 39, 40, 42, 43\}$$
A symmetric solution is $$S
=\{0, 1, 2, 3, 4, 9, 14, 19, 24, 29, 34, 39, 40, 41, 42, 43\}.$$