How many ways we can partition a set S into two subsets such that:
The set $S$ can have $n$ elements in the range $1$ to $1000$ (inclusive). Let the two subsets be $A$ and $B$. For all $x$ in range $1$ to $1000$ we count the number of elements in each subset which are equal to $x$. Let the set $A$ has $a$ elements equal to $x$, and and the set $B$ has $b$ elements of equal to $x$. We compute the sum of all such $a$'s and $b$'s. Now how to determine how many subsets the sum of all $a$'s is more than the sum of all such $b$'s (without actually iterating through all subsets)
Example:
Let $S = \{1, 1, 3, 2\}$ in this cases the answer is $5$. And the subset choice of $A$ are: $\{1,1,3\},\{1,1,2\},\{1,3,2\},\{1,3,2\},\{1,1,3,2\}$
Please note: Either partition can be empty for this problem.
Best Answer
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 ...