Find a Good Subset of the Matrix

Find a Good Subset of the Matrix

This is a problem from LeetCode from the latest biweekly contest.

You are given a 0-indexed m x n binary matrix grid.

Let us call a non-empty subset of rows good if the sum of each column of the subset is at most half of the length of the subset.

More formally, if the length of the chosen subset of rows is k, then the sum of each column should be at most floor(k / 2).

Return an integer array that contains row indices of a good subset sorted in ascending order.

If there are multiple good subsets, you can return any of them. If there are no good subsets, return an empty array.

A subset of rows of the matrix grid is any matrix that can be obtained by deleting some (possibly none or all) rows from grid.

Constraints:

m == grid.length; n == grid[i].length; 1 <= m <= 10^4; 1 <= n <= 5; grid[i][j] is either 0 or 1.

Instead of finding any subset, I misread the problem to be : Find the maximum number of rows that can be selected to form a subset that meet the above condition.

I could not solve this harder version. I wonder if this version can be solved given the constraints. Any help / insight on this is appreciated.