What you tak about are actually not sets, but rather something like this:
For each number $k$, you specify a maximal number $s(k)\in\mathbb N_0$ of occurences. There are only finitely many $k$ with $s(k)\ne 0$.
We want to find all possible choices for functions $a$ such that $0\le a(k)\le s(k)$ for all $k$ and $\sum_k a(k)>\frac12\sum_k s(k)$.
If we drop the condition $\sum_k a(k)>\frac12\sum_k s(k)$ for a moment, there are $\prod_k(s(k)+1)$ possible functions $a$.
Let $\sigma = \sum_k s(k)$. For every $a$ with $\sum_k a(k)<\frac12 \sigma$, its complement has sum $>\frac12\sigma$. Therefore, if $\sigma$ is odd, then the desired number is simply
$$\tag1 \frac12\prod_k(s(k)+1).$$
However, if $\sigma$ is even, we need to explicitly count the number of functions $a$ such that $\sum_k a(k)=\frac12 \sigma$ and then subtract half this number from $(1)$. The counting in this case, I guess, is best done using the techniques of dynamic programming ...
The bivariate generating function of the Stirling numbers of the second kind is given by
$$G(z,u) = \exp(u(\exp(z)-1))$$
so that $$n! [z^n][u^k] G(z, u) = {n \brace k}.$$
If you want to forbid subsets of $r$ elements, mark them and the generating function becomes
$$H(z,u) = \exp\left(uv\frac{z^r}{r!} - u \frac{z^r}{r!} + u(\exp(z)-1)\right)
= \exp\left(uv\frac{z^r}{r!} - u \frac{z^r}{r!}\right)G(z,u).$$
This has the property that the coefficient of $[v^0]$ is the generating function of the partitions with sets of size $r$ not allowed, which is
$$[v^0] H(z, u) = [v^0]
\exp\left(uv\frac{z^r}{r!} \right)
\exp\left(-u\frac{z^r}{r!} \right)
G(z,u) \\=
\exp\left(-u\frac{z^r}{r!} \right)
G(z,u) .$$
Now extracting the coefficient of $[z^n]$ from this we find
$$n! \sum_{q=0}^{\lfloor n/r\rfloor} \frac{1}{q!} \left(-\frac{u}{r!}\right)^q
[z^{n-qr}] G(z, u) .$$
We then obtain for the coefficient of $[u^k]$ the formula
$$n! \sum_{q=0}^{\min(k, \lfloor n/r\rfloor)}
\frac{(-1)^q}{q!\times (r!)^q} [u^{k-q}] [z^{n-qr}] G(z, u)
\\= n! \sum_{q=0}^{\min(k, \lfloor n/r\rfloor)} \frac{1}{(n-qr)!}
\frac{(-1)^q}{q!\times (r!)^q} [u^{k-q}] (n-qr)! [z^{n-qr}] G(z, u) \\
= n! \sum_{q=0}^{\min(k, \lfloor n/r\rfloor)} \frac{1}{(n-qr)!}
\frac{(-1)^q}{q!\times(r!)^q} {n-qr \brace k-q}.$$
This formula gives the number of set partitions of $n$ elements into $k$ sets with subsets of size $r$ not allowed. Subtract this from ${n\brace k}$ to get the number of partitions where there is at least one subset of $r$ elements.
The OEIS has the case of $k=2$ and $r=1$, the case of $k=3$ and $r=1$ and the case of $k=4$ and $r=1$.
Observation. There is an interesting sanity check here, namely what happens when $r>n$. In this case the formula should produce ordinary Stirling numbers because forbidding subsets of a size larger than the total count of available elements does not affect the statistic. And indeed we have $\lfloor n/r \rfloor = 0$ so that only $q=0$ contributes, giving
$$n! \frac{1}{n!}
\frac{1}{1\times(r!)^0} {n\brace k}
= {n\brace k},$$
so the check goes through and we get the correct value.
Best Answer
What you want is the Stirling numbers of the second kind. A Stirling number of the second kind counts the number of ways to partition a set of $n$ objects into $k$ non-empty subsets. It is usually denoted by $\left\{ n \atop k \right\}$.
See the Wikipedia article for methods to compute such numbers.