【Java】2 Solutions Using Backtracking (+Pruning)
Solution 1: Choose or Not ChooseCodeSolution 2: Pickup One Col from Remaining ColsCode
# Solution 1: Choose or Not Choose
![2397-1.jpg](https://assets.leetcode.com/users/images/5e9d3cf3-157c-40d3-8546-d4dbc62b1979_1740156649.3141794.jpeg)
# Code
```java []
class Solution {
    int max;
    boolean[] selected; // record selected cols
    int selectedNum;
    int m,n;

    public int maximumRows(int[][] matrix, int numSelect) {
        // init
        max = 0;
        // selected = new boolean[n];
        selectedNum = 0;
        m = matrix.length;
        n = matrix[0].length;
        selected = new boolean[n];
        
        // use backtrack to try all possible combinations of cols
        dfs(0, matrix, numSelect);

        return max;
    }

    // ith col choose or not choose
    private void dfs(int i, int[][] matrix, int numSelect){
        // end condition
        if(selectedNum == numSelect || i == n){
            int coveredNum = 0;
            // check row-by-row
            for(int x=0; x<m; x++){
                boolean covered = true;
                for(int y=0; y<n; y++){
                    if(matrix[x][y] == 1 && !selected[y]){
                        covered = false;
                        break;
                    }
                }
                if(covered) coveredNum++;
            }
            max = Math.max(max, coveredNum);
            return;
        }

        // choose
        selected[i] = true;
        selectedNum++;
        dfs(i+1, matrix, numSelect);
        // backtrack
        selected[i] = false;
        selectedNum--;

        // not choose 
        // Pruning here!! (not-choose branch)
        if(i <= n-1-numSelect+selectedNum){
            dfs(i+1, matrix, numSelect);
        }
    }
}
```

# Solution 2: Pickup One Col from Remaining Cols
![2397-2.jpg](https://assets.leetcode.com/users/images/c4bf7c74-0549-433a-9d97-83d0998369b0_1740156776.089486.jpeg)


# Code
```java []
class Solution {
    int m,n;
    boolean[] choosedCols;
    int selectedNum;
    int max;

    public int maximumRows(int[][] matrix, int numSelect) {
        // init
        m = matrix.length;
        n = matrix[0].length;
        choosedCols = new boolean[n];
        selectedNum = 0;

        // use backtrack to try out all possible combinations of selected cols
        dfs(0, numSelect, matrix);
        
        return max;
    }

    private void dfs(int startIdx, int numSelect, int[][] matrix){
        // end condition
        if(selectedNum == numSelect || startIdx == n){
            max = Math.max(max, checkCoveredRows(matrix));
            return;
        }

        // pick a col from remaining cols
        // Pruning here!! (for loop)
        for(int i=startIdx; i <= n-numSelect+selectedNum; i++){
            // choose
            choosedCols[i] = true;
            selectedNum++;
            dfs(i+1, numSelect, matrix);
            choosedCols[i] = false;
            selectedNum--;
        }
    }

    private int checkCoveredRows(int[][] matrix){
        int rows = 0;
        for(int row=0; row<m; row++){
            boolean covered = true;
            // start checking cols
            for(int col=0; col<n; col++){
                if(matrix[row][col] == 1 && !choosedCols[col]){
                    covered = false;
                    break;
                }
            }

            if(covered) rows++;
        }
        return rows;
    }
}
```

['Java']