World's most popular travel blog for travel bloggers.

# 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\$

, ,
Problem Detail:

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?

#### Answered By : Yuval Filmus

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.