Backtracking | Java Solution | Code with comments
Idea is to use backtraking. But before trying that we should know how to calculate which all rows are not covered by choosen columns. For that we can store this
Idea is to use backtraking. But before trying that we should know how to calculate which all rows are not covered by choosen columns. For that we can store this info in a map (column index to set of row indices haiving one). For each possible combination in backtraking we calculate which all rows were missed and substract if from total number of rows.\n\n\n```\nclass Solution {\n    int result;\n    public int maximumRows(int[][] mat, int cols) {\n        int m = mat.length; // number of rows\n        int n = mat[0].length; // number of columns\n        result = -1;\n\n        // if cols is equal to number of columns andswer will be number of rows.\n        if(cols == n) return m;\n\n        // Map to store which column index covers which all rows having value 1.\n        Map<Integer, Set<Integer>> columnIndexToRowHavingOnes = new HashMap<>();\n\n        for(int i = 0; i < n; i++) columnIndexToRowHavingOnes.put(i, new HashSet<>());\n        for(int i = 0; i < m; i++){\n            for(int j = 0; j < n; j++){\n                if(mat[i][j] == 1) {\n                    Set<Integer> set = columnIndexToRowHavingOnes.get(j);\n                    set.add(i);\n                    columnIndexToRowHavingOnes.put(j, set);\n                }\n            }\n        }\n\n        getAnswer(0, new ArrayList<Integer>(), cols, columnIndexToRowHavingOnes, m, n);\n\n        return result;\n    }\n\n    // Backtracking function\n    private void getAnswer(int index, ArrayList<Integer> colChoosen, int cols, Map<Integer, Set<Integer>> columnIndexToRowHavingOnes, int m, int n){\n\n        // If we have chossed cols number of columns\n        if(colChoosen.size() == cols){\n            Set<Integer> rowNotCoveredByChoosenColumns = new HashSet<>();\n            // For each column\n            for(int i = 0; i < n; i++){\n                // find which all rows were missed which have value 1\n                if(!colChoosen.contains(i)){\n                    rowNotCoveredByChoosenColumns.addAll(columnIndexToRowHavingOnes.get(i));\n                }\n            }\n\n            result = Math.max(result, m - rowNotCoveredByChoosenColumns.size());\n            return;\n        }\n\n        if(index == n) return;\n\n        // pick the column\n        colChoosen.add(index);\n        getAnswer(index + 1, colChoosen, cols, columnIndexToRowHavingOnes, m, n);\n\n        // unpick the column\n        colChoosen.remove(colChoosen.size() - 1);\n        getAnswer(index + 1, colChoosen, cols, columnIndexToRowHavingOnes, m, n);\n\n    }\n}\n```
['Backtracking', 'Java']