When I slept soundly last night, a dream took me back to the times when I was taking my college entrance contest. I was given this problem:

Let $$$n$$$ be a positive integer and $$$S$$$ be a multiset of $$$\{1, 2, ..., n\}$$$. Integer $$$i\,(1 \leq i \leq n)$$$ appears $$$a_i \geq 0$$$ times in $$$S$$$. Also, I was given a positive integer $$$k$$$. A partition of $$$S$$$, namely $$$\cup_{i=1}^t S_i$$$ is valid iff all of the following three conditions hold:

(1) $$$\cup_{i=1}^t S_i = S$$$.

(2) $$$\forall 1 \leq i < j \leq t,\,S_i \neq S_j$$$

(3) $$$\forall 1 \leq i \leq t$$$, the size of $$$S_i$$$ is less or equal than $$$k$$$, i.e., $$$|S_i| \leq k$$$.