# 2397. Maximum Rows Covered by Columns¶

• Time: $O(mn \cdot 2^n)$
• Space: $O(2^n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public: int maximumRows(vector>& matrix, int numSelect) { int ans = 0; dfs(matrix, /*colIndex=*/0, numSelect, /*mask=*/0, ans); return ans; } private: void dfs(const vector>& matrix, int colIndex, int leftColsCount, int mask, int& ans) { if (leftColsCount == 0) { ans = max(ans, getAllZerosRowCount(matrix, mask)); return; } if (colIndex == matrix[0].size()) return; // Choose this column. dfs(matrix, colIndex + 1, leftColsCount - 1, mask | 1 << colIndex, ans); // Don't choose this column. dfs(matrix, colIndex + 1, leftColsCount, mask, ans); } int getAllZerosRowCount(const vector>& matrix, int mask) { int count = 0; for (const vector& row : matrix) { bool isAllZeros = true; for (int i = 0; i < row.size(); ++i) { if (row[i] == 1 && (mask >> i & 1) == 0) { isAllZeros = false; break; } } if (isAllZeros) ++count; } return count; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public int maximumRows(int[][] matrix, int numSelect) { dfs(matrix, /*colIndex=*/0, numSelect, /*mask=*/0); return ans; } private int ans = 0; private void dfs(int[][] matrix, int colIndex, int leftColsCount, int mask) { if (leftColsCount == 0) { ans = Math.max(ans, getAllZerosRowCount(matrix, mask)); return; } if (colIndex == matrix[0].length) return; // Choose this column. dfs(matrix, colIndex + 1, leftColsCount - 1, mask | 1 << colIndex); // Don't choose this column. dfs(matrix, colIndex + 1, leftColsCount, mask); } int getAllZerosRowCount(int[][] matrix, int mask) { int count = 0; for (int[] row : matrix) { boolean isAllZeros = true; for (int i = 0; i < row.length; ++i) { if (row[i] == 1 && (mask >> i & 1) == 0) { isAllZeros = false; break; } } if (isAllZeros) ++count; } return count; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution: def maximumRows(self, matrix: list[list[int]], numSelect: int) -> int: ans = 0 def dfs(colIndex: int, leftColsCount: int, mask: int): nonlocal ans if leftColsCount == 0: ans = max(ans, self._getAllZerosRowCount(matrix, mask)) return if colIndex == len(matrix[0]): return # Choose this column. dfs(colIndex + 1, leftColsCount - 1, mask | 1 << colIndex) # Don't choose this column. dfs(colIndex + 1, leftColsCount, mask) dfs(0, numSelect, 0) return ans def _getAllZerosRowCount(self, matrix: list[list[int]], mask: int) -> int: count = 0 for row in matrix: isAllZeros = True for i, cell in enumerate(row): if cell == 1 and (mask >> i & 1) == 0: isAllZeros = False break if isAllZeros: count += 1 return count