✅✅Faster || Easy To Understand || C++ Code
Backtracking\n\n Time Complexity :- O(N * M * 2 ^ M)\n\n Space Complexity :- O(N * M * 2 ^ M)\n\n\nclass Solution {\npublic:\n    \n    // res will store all th
* ***Backtracking***\n\n* ***Time Complexity :- O(N * M * 2 ^ M)***\n\n* ***Space Complexity :- O(N * M * 2 ^ M)***\n\n```\nclass Solution {\npublic:\n    \n    // res will store all the subsequence of size k\n    \n    vector<vector<int>> res;\n    \n    vector<int> curr;\n    \n    // function for finding subsequence of an array\n    \n    void dfs(vector<int>& arr, int i, int n, int k)\n    {\n        // base case\n        \n        if(i == n)\n        {\n            if(curr.size() == k)\n            {\n                res.push_back(curr);\n            }\n            \n            return;\n        }\n        \n        // for every no. we have two options either we can include or exclude\n        \n        // inclusion part\n        \n        curr.push_back(arr[i]);\n        \n        dfs(arr, i + 1, n, k);\n        \n        curr.pop_back();\n        \n        // exclusion part\n        \n        dfs(arr, i + 1, n, k);\n    }\n    \n    int maximumRows(vector<vector<int>>& mat, int cols) {\n        \n        int n = mat.size();\n        \n        int m = mat[0].size();\n        \n        // declare and initialize a col_arr\n        \n        vector<int> col_arr(m, 0);\n        \n        for(int i = 0; i < m; i++)\n        {\n            col_arr[i] = i;\n        }\n        \n        // find all the subsequece of columns of size cols\n        \n        dfs(col_arr, 0, m, cols);\n        \n        // now for every column combination find the maximum row we can covered\n        \n        int maxi = INT_MIN;\n        \n        for(int k = 0; k < res.size(); k++)\n        {\n            vector<int> temp = res[k];\n            \n            unordered_set<int> s(temp.begin(), temp.end());\n            \n            int count = 0;\n            \n            // check every row can we covered or not\n            \n            for(int i = 0; i < n; i++)\n            {\n                bool flag = true;\n                \n                for(int j = 0; j < m; j++)\n                {\n                    if(mat[i][j])\n                    {\n                        if(s.count(j) == 0)\n                        {\n                            flag = false;\n                            \n                            break;\n                        }\n                    }\n                }\n                \n                if(flag)\n                {\n                    count++;\n                }\n            }\n            \n            // update maxi\n            \n            maxi = max(maxi, count);\n        }\n        \n        return maxi;\n    }\n};\n```
['Backtracking', 'Recursion', 'C', 'C++']