A weighted set cover problem is:
Given a universe $U=\{1,2,...,n\}$ and a collection of subsets of $U$, $\mathcal S=\{S_1,S_2,...,S_m\}$, and a cost function $c:\mathcal S\to Q^+$ , find a minimum cost subcollection of $\mathcal S$ that covers all elements of $U$.
The question is how to design a deterministic algorithm to solve weight set cover in $O(2^n)$ (just find the optimum solution)?
If I simply use exhaust searching to look through all possible cover (which is actually equals to $2^m$) and find the one with minimum weight, it will cost $O(2^m)$ but not $O(2^n)$.
Thanks in advanced!
After some experiment I find that when a the $\mathcal S$ is acutally equals to the power set of the universe $U$($m=2^n$),there are less than $2^n$ combination of the power set of $\mathcal S$($2^{n^n}$) can cover the universe $U$. But how can I prove that the coverable combination of $\mathcal S$ is less than $2^n$?