Partitions restricted to only certain summands Here $n$ is a positive integer and $p(n)$ is the number of unrestricted partitions.

Can one always find a subset $s$, of $\{1,2,\ldots,n\}$ such that the number of partitions of $n$ with parts from $s$ is $p(n)/2$ if $p(n)$ is even and is $[p(n)+1]/2$ or $[p(n)-1]/2$ if $n$ is odd?

For example: if $n=7$ we may choose $s$ to be $\{1,3,4,5,7\}$.  The partitions of 7 which are to be counted are
$$
\begin{split}
&7\\
&5+1+1\\
&4+3\\
&3+3+1\\
&4+1+1+1\\
&3+1+1+1+1\\
&1+1+1+1+1+1+1\\
\end{split}
$$
and $[p(n)-1]/2= (15-1)/2=7$  so we can do what was asked of us.
 A: Not a proven answer, but evidence that the problem can always be solved fairly easily and a suspicion that a much stronger result is true.
Using a greedy approach, I was able to construct the desired set $S$ for each $n$ with $p(n)$ even up to $n=50$ (I focused on the even case since they have a single target value).  Write $p_S(n)$ for the number of partitions of $n$ with parts from $S$.


*

*Given $n \ge 2$, find the smallest $k$ so that $p_{\{1,\ldots, k\}}(n) > p(n)/2$.

*Consider $S=\{1,\ldots,k-1,k+1\}$, $\{1,\ldots,k-1,k+2\}$, etc., to the first occurrence of $P_S(n) \le p(n)/2$.  Let $\ell$ be the new part and set $S=\{1,\ldots,k-1,\ell\}$.

*If $p_S(n) < p(n)/2$, then repeat Step 2 considering $S = \{1,\ldots,k-1,\ell,\ell+1\}$, $\{1,\ldots,k-1,\ell,\ell+2\}$, etc.


For example, this procedure for $n = 50$ leads to $S=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 20, 32, 46\}$.  
It's not apparent that the algorithm gives an $S$ for which $p_S(n)$ lands exactly on $p(n)/2$.  The intuition for why it works is that allowing large parts (close to $n$) increases the partition count by a small number, allowing fine adjustments to $p_S(n)$.  In the $n=50$ example, $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 20, 32, 47\}$ gives 102,111 rather than the desired 102,113.  Then $S=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 20, 32, 47, 48\}$ gives a different set with $p_S(n) = p(50)/2$.
The fact that no backtracking was required through $n=50$ suggests that there are several choices for $S$.  Further, there does not seem to be anything special about the values $p(n)/2$, $(p(n) \pm 1)/2$.  I verified for $n=19$ that for every $k$ satisfying $1 \le k \le p(19) = 490$, there is an $S$ for which $p_S(n) = k$.  

Could it be that, given $n$ and any $k$ with $1 \le k \le p(n)$, there
  is always an $S \subseteq \{1, \ldots, n\}$ such that $p_S(n) = k$?

Certainly the number of subsets grows much faster than $p(n)$...
