How to find all maximal sets $S_i$ of a given array $T$ such that every element of $S_i$ is greater than or equal to the cardinality of $S_i$

Question

Lately, I asked this question to find the maximal set of elements $S$ of a given array $T$ such that every element of $S$ is greater than or equal to the cardinality of $S$.

My question is now different. How to find all maximal sets $S_i$ of a given array $T$ such that every element of $S_i$ is greater than or equal to the cardinality of $S_i$.

For example, if $T=[9, 8, 2, 2, 1],ドル then all maximal sets that satisfy the condition are $S_1=[9, 8],ドル $S_2=[9, 2],ドル $S_3=[9, 2],ドル $S_4=[8, 2],ドル $S_5=[8, 2]$ and $S_6=[2, 2]$.

My recursive solution or the solutions given in the previous question do not generate all maximal sets.

Is there any efficient algorithm that finds all maximal sets of such problem?

I think one way to solve the problem is to find a maximal set $S$ and return its size $|S|$--using any algorithm from this question. Then, generate all combinations $\displaystyle\binom{|T|}{|S|}$ and find which one of these combinations satisfies the condition. But can we do better?

• Karolis Juodelė: Obviously, you can drop 1 from T, once you know that |S|=2. Other than that (and some duplicate handling), there is nothing to improve. There really are that many maximal sets.
• Yuval Filmus: What do you mean by maximal set? Maximum size, or inclusion-maximal?

Answer 1

Assuming that by maximal sets you mean sets of maximal size (rather than sets which are inclusion-maximal), then there is a very simple algorithm. First, find the maximal size $s$. Second, filter out all elements smaller than $s$. Third, output all subsets of size $s$ of the remaining elements.

• drzbir: Good. I think this works fine. Thanks.