Given a collection C of subsets of a finite set S, a hitting set for C is a set S' that such S' is a subset of S and S' contains at least one element from each set in C.

Write a program that returns all the hitting sets for a collection of finite sets C, with the assumption that S is the union of all sets in C.
2 months later
So I just went back and parsed the math in this exercise into C# types:
Given 
List<int> S: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ..., n]
List<List<int>> C: [[1, 3, 4, 6], [4, 6, 8], [6, 8, 9, 10, 11], [10, 11] ...]
with the assumption that S is the union of all sets in C. This statement means that you'll have to build up S from C by concatenation, and it most probably allows something for the optimization.

The result must be of type List<List<int>>. Each list of the result, which is a hitting set, must contain at least one element from each List in C.

My Solution Plan If Ever
If I will ever attack this problem, I would start by removing the duplicates from each element of the lists.
Example: If we had: C = [[1], [1, 2, 3], [1, 4, 5]], the hitting sets for it would be the same for the following set of sets:
[[1], [2, 3], [4, 5]].

The rest is a matter of combinations, nested under a mandatory pass through of each of the resulting nonempty sets.
I remember back in college there was like a 50 paper research on hitting sets. Damn you geek! :-(
I think it'd be more interesting if you could define C and S in the beginning. We could start working on a particular case, and then move on to a generalization to the nth.

What do you think?
The nth is not necessary. I only included it as a means to mean that it's actually not important. It seems the trick is all in C. You can consider my "...n" as whatever, as long as each list in C is a subset of S. When we discard S from the input, and build it implicitly, the above statement becomes unnecessary.

To rephrase:
Given a List<List<int>> C, you can build S which is the union of the elements of C. The type of S is List<int> (can be inferred from last statement).
The next step I am taking is to make the lists inside C mutually exclusive while preserving the invariance of the output. I do that by picking each element from each list and removing it from every other list.

All the combinations of a given set are 2^n = product of (2 ^ n_each_set).

The purpose of my above post is to validate from geek that I understood the problem correctly before I attempt to solve it. But now it seems that there's nothing actually special.
if you construct a partition C' of S and use it instead of C, you'll end up with a different result.

example:
C = {{1}, {1, 2}, {1, 2, 3}}
C' = {{1}, {2}, {3}}
HS(C) = {{1}, {1, 2}, {1, 3}, {1, 2, 3}}
HS(C') = {{1, 2, 3}}

this approach becomes interesting when we want a minimum hitting set.
xterm wroteI remember back in college there was like a 50 paper research on hitting sets. Damn you geek! :-(
indeed, since the decision version of the minimum hitting set problem is NP-complete.
Ah so I see I was too eager in the duplicate elimination. It should be catered for while creating sets in the hitting set.