Counting subsets of given set with certain properties
If $S = \{2,2\}$ and $k=1$, the answer is $2$, the following dynamic program works.

Let $S = \{a_1,a_2,...,a_{|S|}\}$ where $a_i \leq a_{i+1}$. Consider the function $DP(i,n)$ as the number of satisfying subsets ending with element $i$ of length $n$. A satisfying set is a set $T = \{s_1,s_2,...,s_{k'}\}$ with the property $i \leq s_i \leq s_{i+1}$.

Hence, $DP(i,n) = 0$ if $a_i \leq n$, $1$ if $n = 1$. Otherwise, $DP(i,n) = \sum_{j=1}^{i-1} DP(j,n-1)$. The answer will then be $\sum_{j=1}^{|S|} DP(j,k)$.

If indeed for the case  $S = \{2,2\}$ and $k=1$, the answer is $1$. A small modification to the above recurrence is possible. Consider a representation of a multiset $S$ in the form $\{(a_1,b_1),(a_2,b_2),...,(a_n, b_n)\}$ where $a_i &lt; a_{i+1}$ and $b_i$ is the number of copies of $a_i$ in $S$.