NO BITMASK | Full Intuition✅Backtracking | C++
IntuitionStraight forward backtracking, only covered rows calculation is bit tricky and difficult to understandApproach
Generate all possible cols subset of siz
# Intuition
Straight forward backtracking, only covered rows calculation is bit tricky and difficult to understand

# Approach
1. Generate all possible cols subset of size exactly numSelect
2. A row is only considered valid, if all of the 1's that are present in that row, is in our current subset of cols

# Complexity
- Time complexity:
$$O(2^n * (m*n))$$, n = columns

- Space complexity:
$$O(n)$$

# Code
```cpp []
class Solution {
public:
    int findScore(set<int>& col, vector<vector<int>>& matrix) {
        
        int cur = 0; // current covered rows
        for(int i = 0; i < matrix.size(); i++) {
            bool f = true; // assume row is covered

            for(int j = 0; j < matrix[0].size(); j++) {
                // if current row has a value 1, and col of that row is not present in 
                // subset of cols, row not covered
                if (matrix[i][j] == 1 && col.count(j) == 0) {
                    f = false;
                    break;
                }
            }
            if (f) cur++;
        }
        return cur;
    }

    void solve(int i, int m, vector<vector<int>>& matrix, int n, set<int>& col, int& mx) {

        // no columns left
        if (i == m) {
            // if selected exactly n columns
            if (col.size() == n) {
                // update score
                mx = max(mx, findScore(col, matrix));
            }
            return;
        }

        // pick column
        col.insert(i);
        solve(i+1, m, matrix, n, col, mx);
        col.erase(i);

        // not pick col
        solve(i+1, m, matrix, n, col, mx);
    }

    int maximumRows(vector<vector<int>>& matrix, int numSelect) {
        // choose all possible ways of selecting numSelect columns from all possible cols
        // total_col C numSelect_col (C means combination)
        // we try generating all subsets of size exactly numSelect
        // and contains column indices

        // for each such subsets calculate covered rows
        // we calculate covered rows, by checking whether for each row
        // all 1's in that row has its column present in subset cols
        // so if one row has only value 1 in mat[i][j], then j should be in subset cols
        // we count all such rows + rows with no 1's
        // get the max out of them

        set<int> col;
        int m = matrix[0].size(); // number of columns
        int mx = 0;
        solve(0, m, matrix, numSelect, col, mx);
        return mx;
    }
};
```
['Backtracking', 'Matrix', 'C++']