Diverse Subset. A store trying to analyze the behavior of its customers will often maintain a two$-$dimensional array A$,$ where the rows correspond to its customers and the columns correspond to the products it sells. The entry A$[$i$,$ j$]$ specifies the quantity of product j that has been purchased by customer i$.$

Here$$s a tiny example of such an array A$.$

detergent

beer

diapers

cat litter

Raj

Alanis

Chelsea

$0$

$2$

$0$

$6$

$3$

$0$

$0$

$0$

$0$

$3$

$0$

$7$

One thing that a store might want to do with this data is the following. Let us say that a subset S of the customers is diverse if no two of the of the customers in S have ever bought the same product $($i$.$e$.,$ for each product, at most one of the customers in S has ever bought it$).$ A diverse set of customers can be useful, for example, as a target pool for market research.

We can now define the Diverse$-$Subset Problem as follows: Given an m $\backslash$times n array A as defined above, and a number k $<=$ m$,$ is there a subset of at least k of customers that is diverse?