Check all subsets using Bit Masking
According to the problem if we select a set of columns then \n\nFor ith row(matrix[i]) to be valid:\n\n1. If the jth col is selected: \n    we don\'t care if th
According to the problem if we select a set of columns then \n\n**For ith row(matrix[i]) to be valid:**\n\n**1. If the jth col is selected:** \n    we don\'t care if there are `0` or `1` in matrix[i][j].\n**2. If the jth column is not selected**\n`if(matrix[i][j]==1)` then that row will be invalid for those set of selected columns\n\n**# Conclusion:**\nFind no. of valid rows i.e  `mat[i][j] = 0 for all unselected coloumns` for all possible combinations of columns and take the maximum of all combinations.\n\nI commented the code so that it become easy for you to understand, a basic understanding of bit operations is required.\n\n# Code\n```\nclass Solution {\npublic:\n    int maximumRows(vector<vector<int>>& matrix, int k) {\n        \n        int m = matrix.size();\n        int n = matrix[0].size();\n\t\tint subset_ct = (1<<n);     //Total subset (2^n)\n\n        int ans = 0;\n\t\tfor(int mask = 1; mask < subset_ct; mask++){    //Iterate for each subset possible\n\t\t\tif(__builtin_popcount(mask)==k){    //If exact k col are selected\n                int temp = m;       //Initially mark all the row valid\n                for(int i=0;i<m;i++){   //For a possible combination of col check the no. of valid rows\n                    for(int j=0;j<n;j++){\n                        if(!(mask&(1<<j)) && matrix[i][n-j-1]==1) {temp--; break;}\n                    }\n                }\n                ans = max(ans,temp);\n            }\n\t\t}\n\n        return ans;\n    }\n};\n```
['Bit Manipulation', 'C++']