# Algorithm to find minimum number of elements that occur in all sets

I have `n` sets that each contain some elements, for example:

`{2, 3}, {6, 3}, {2, 7, 3}, {7}`

Now the goal is to find the minimum number of elements that occur in all sets. For this example it would be 2 (`{3, 7}`). Some more examples:

`{2}, {4}` - minimum is 2 (`{2, 4}`)
`{4, 15, 3}, {3, 2}, {24, 4, 2}, {24}, {15, 6}` - minimum is 3 (`{15, 2, 24}` or `{15, 3, 24}` or `{3, 24, 6}`)

I don't need to know the set of those minimum number of elements necessarily, just the size of that set is enough.

I've written a recursive algorithm myself already that goes over all possibilities, but the execution time really gets out of hand as the number of different elements rises. Is there an algorithm available (maybe already written but I couldn't find it) for this specific problem? I've looked at the set cover problem, it looks a bit like this one but it's not exactly the same.

• This could be a better fit on Code Review if you were to post your current code. Oct 5, 2020 at 14:38
• Thinking aloud: I would take an iterative approach. You `resultSet` starts with all elements that are members of singleton sets. In your original example, `7`. Then, I would remove `7` from all sets (removing `{7}` entirely rather than leaving it empty), and calculate the intersection of all remaining sets. If the intersection is empty, you find the smallest set, and add all of its elements to the result, and repeat. If it's not empty (in this case, it will be `{3}`), remove the intersection elements from all sets. Repeat until all original sets are "checked off". Oct 5, 2020 at 14:58
• This might be more appropriate for cs.stackexchange.com who deal more with these kinds of cs/algorithm problems. Their answers are more language agnostic (psuedo-code and such), but should set you in the right direction with regards to the overall approach Oct 5, 2020 at 15:00
• Never mind, my greedy approach takes too many elements. The intersection of all remaining sets contains more elements than strictly necessary. Of each such intersection, only one of its elements is necessary to "hit" all of the input sets. Picking one of them strategically is ... hard. Oct 5, 2020 at 15:27