2732. Find a Good Subset of the Matrix Hard

1/**
2 * [2732] Find a Good Subset of the Matrix
3 *
4 * You are given a 0-indexed m x n binary matrix grid.
5 * 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.
6 * 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).
7 * Return an integer array that contains row indices of a good subset sorted in ascending order.
8 * If there are multiple good subsets, you can return any of them. If there are no good subsets, return an empty array.
9 * 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.
10 *  
11 * <strong class="example">Example 1:
12 * 
13 * Input: grid = [[0,1,1,0],[0,0,0,1],[1,1,1,1]]
14 * Output: [0,1]
15 * Explanation: We can choose the 0^th and 1^st rows to create a good subset of rows.
16 * The length of the chosen subset is 2.
17 * - The sum of the 0^th column is 0 + 0 = 0, which is at most half of the length of the subset.
18 * - The sum of the 1^st column is 1 + 0 = 1, which is at most half of the length of the subset.
19 * - The sum of the 2^nd column is 1 + 0 = 1, which is at most half of the length of the subset.
20 * - The sum of the 3^rd column is 0 + 1 = 1, which is at most half of the length of the subset.
21 * 
22 * <strong class="example">Example 2:
23 * 
24 * Input: grid = [[0]]
25 * Output: [0]
26 * Explanation: We can choose the 0^th row to create a good subset of rows.
27 * The length of the chosen subset is 1.
28 * - The sum of the 0^th column is 0, which is at most half of the length of the subset.
29 * 
30 * <strong class="example">Example 3:
31 * 
32 * Input: grid = [[1,1,1],[1,1,1]]
33 * Output: []
34 * Explanation: It is impossible to choose any subset of rows to create a good subset.
35 * 
36 *  
37 * Constraints:
38 * 
39 * 	m == grid.length
40 * 	n == grid[i].length
41 * 	1 <= m <= 10^4
42 * 	1 <= n <= 5
43 * 	grid[i][j] is either 0 or 1.
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/find-a-good-subset-of-the-matrix/
49// discuss: https://leetcode.com/problems/find-a-good-subset-of-the-matrix/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn good_subsetof_binary_matrix(grid: Vec<Vec<i32>>) -> Vec<i32> {
55        vec![]
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_2732() {
67    }
68}
69