Given the multiset $S$ where the elements are defined by the binomial coefficient ${n \choose k}$ where $n \in \mathbb{N}$ and $ 0\leq k \leq n$ find the partition $P$ of $S$ such that the sum of elements in the subsets is smaller or equal to the largest binomial coefficient and the number of subsets in the partition is minimized.
For example take $n = 4$.
$S = \{{4 \choose 0}, {4 \choose 1}, {4 \choose 2}, {4 \choose 3}, {4 \choose 4} \} = \{ 1, 4, 6, 4, 1\}$
Then the partitions
$P = \{ \{4,1\},\{4,1\}, \{6\} \}$
$Q = \{ \{4,1,1\},\{4\}, \{6\} \}$
are the partitions we are looking for. The largest binomial coefficient $6$ has to be on it's own by definition. Then we have $\{1,4,4,1\}$ left and there cannot be any sum larger then six so we have make two sets of $\{1,4\}$ or make the set $\{1,4,1\}$ once and $\{4\}$. I am more interested in getting the $P$ then $Q$ since the sums are closer together but this is not a hard requirement.
I wonder if a non brute-force algorithm exists for this since we do know a little bit of the contents.
