Permutations v/s Subsets
1. Using Subsets - \n- We can just simply Check all subsets which have K setbits (i.e K columns selected)\n- Time Complexity : O(2^(Columns) * Rows * Columns)\n
# 1. Using Subsets - \n- We can just simply Check all subsets which have K setbits (i.e K columns selected)\n- **Time Complexity :** O(2^(Columns) * Rows * Columns)\n- **Space Complexity :** O(1)\n```\nclass Solution {\npublic:\n    int maximumRows(vector<vector<int>> &A , int K){\n        int Rows = A.size() , Cols = A[0].size();\n        int maxRowsCovered = 0;\n        for(int mask = (1 << K) - 1 ; mask < (1 << Cols) ; mask++){\n            if(__builtin_popcount(mask) == K){\n                int currRowsCovered = 0;\n                for(int Row = 0 ; Row < Rows ; Row++){\n                    int isRowCovered = 1;\n                    for(int Col = 0 ; Col < Cols ; Col++){\n                        if(A[Row][Col] && (mask >> Col & 1 ^ 1)){\n                            isRowCovered = 0;\n                            break;\n                        }\n                    }\n                    if(isRowCovered) currRowsCovered += 1;\n                }\n                maxRowsCovered = max(maxRowsCovered , currRowsCovered);\n            }\n        }\n        return maxRowsCovered;\n    }\n};\n```\n\n# 2. Using Permutations - \n- `Idea :` Subsets with K-SetBits = PermuationsOf(`000111....(K-times)`)\n- Instead of going through all subsets and considering Subsets with K-SetBits , we can `skip Non-K-SetBits Subsets Using Permutations `\n- In subsets approach our first mask with K-SetBits is `000111....(K-times)`\nAnd it will be same in permutations approach as well ,\nbecause `000111....(K-times)` is the lexicographically smallest valid permutation and from this permutation we can get all Subets with K-SetBits using Next Permutation.\n- **Time Complexity :** O(NCR(Columns , K) * Rows * Columns)\n- **Space Complexity :** O(1)\n- `NOTE : NCR(Columns , K) will be atmask 924 which is NCR(12 , 6)`\n```\nclass Solution {\npublic:\n    int maximumRows(vector<vector<int>> &A , int K){\n        int Rows = A.size() , Cols = A[0].size();\n        int maxRowsCovered = 0;\n        string P = string(Cols - K , \'0\') + string(K , \'1\');\n        do{\n            int currRowsCovered = 0;\n            for(int Row = 0 ; Row < Rows ; Row++){\n                int isRowCovered = 1;\n                for(int Col = 0 ; Col < Cols ; Col++){\n                    if(A[Row][Col] && P[Col] == \'0\'){\n                        isRowCovered = 0;\n                        break;\n                    }\n                }\n                if(isRowCovered) currRowsCovered += 1;\n            }\n            maxRowsCovered = max(maxRowsCovered , currRowsCovered);\n        }while(next_permutation(P.begin() , P.end()));\n        return maxRowsCovered;\n    }\n};\n```
['Bit Manipulation', 'Combinatorics', 'Bitmask', 'C++', 'Java', 'Python3']