Every possible number of partitions by restricting parts?

The conjecture seems to hold.

For brevity, denote $[k,n]=\{k,k+1,\dots,n\}$ and $[n]=[1,n]$. Start with $S = [n]$.

Algorithm: Given $0\leq k\leq p(n)$, consider the numbers $1,2,\dots,n$ one by one, removing the number if the remaining set $S$ satisfies $p_S(n)\geq k$. After all $n$ numbers are considered, we are done.

Let $S_m$ be the set obtained after considering the numbers up to $m$. Hence, the algorithm reads as follows: $S_m=S_{m-1}\setminus\{m\}$ if $p_{S_{m-1}\setminus\{m\}}(n)\geq k$, and $S_m=S_{m-1}$ otherwise.

We claim that at each step, the inequality $$ p_{S_m\cap[m]}(n)\leq k \qquad(*) $$ holds. If $(*)$ is proved, we will get $k\leq p_{S_n}(n)\leq k$, as required.

We prove $(*)$ by induction on $m$. Clearly, it holds for $m=0$. Assume now that $p_{S_{m-1}\cap[m-1]}(n)\leq k$. If $S_m=S_{m-1}\setminus\{m\}$, then $S_{m-1}\cap[m-1]=S_m\cap[m]$, and $(*)$ holds. Otherwise, $S_m=S_{m-1}$, which means that $p_{S_{m-1}\setminus\{m\}}(n)\leq k-1$. So, in order to finish this case, it suffices to show that $$ p_{S\cap[m]}(n)\leq p_{S\setminus\{m\}}(n)+1 \qquad(**) $$ for every $S\supseteq[m,n]$ (and apply it to $S=S_{m-1}$). If $m=n$, the inequality is obvious. Otherwise, we will show even the version without `$+1$'.

We present an ``injective'' proof, after taking the complements. Namely, to each partition with parts in $S$, at least one of which equals $m$, we assign a partition with parts in $S$, at least one of which exceeds $m$, so that this correspondence is injective. This will prove $$ p_S(n)-p_{S\setminus\{m\}}(n)\leq p_S(n)-p_{S\cap[m]}(n), $$ which yields $(**)$.

The partitions containing both $m$ and $>m$ correspond to themselves. Now take any partition with maximal element $m$. If it contains a unique copy of $m$, let $a(<m)$ be the minimal element of the partition; replace now $m$ and $a$ by $m+a$. Finally, if the partition contains exactly $d>1$ copies of $m$, replace them by $dm$. Clearly, this correspondence is injective, as required.