C++ Easy to Understand BackTracking Solution
Intuition:  We will consider all possible combinations of choosing the "cols" amount of columns. For each such combination, we will find the number of covered r
Intuition:  We will consider all possible combinations of choosing the "cols" amount of columns. For each such combination, we will find the number of covered rows and choose the combination that gives the maximum number of covered rows.\n\nApproach: For considering all possible combinations of choosing columns, let\'s use recursion + backtracking. On each call, we will have two options: \n1. Not to Choose this Column - make a call on the next column.\n2. Choose this Column - mark this column as selected and call on the next column.\n\nBase Cases:\n1. We have selected all required columns.\n2. Columns size is exhausted and we haven\'t chosen the required amount of columns.\n\nRemember that we **must** choose "cols" number of columns.\n\n**C++**\n```\nclass Solution {\nprivate:\n    int ans;\n    \n    void helper(vector<vector<int>>& mat, vector<int> &chose, int c, int n, int m, int cols) {\n        if(cols == 0) { // We choose all required columns\n            int cntRows = calcRow(mat, chose, n, m);\n            ans = max(ans, cntRows);\n            return;\n        }\n        \n        if(c >= m) { // if column size is exhausted and we haven\'t chosen the required amount of columns\n            return;\n        }\n        \n        helper(mat, chose, c + 1, n, m, cols); // not choosing this column\n        \n\t\t// choose this column\n        chose[c] = 1; // mark this column\n        helper(mat, chose, c + 1, n, m, cols - 1);\n        chose[c] = 0; // unmark this column\n    }\n    \n    int calcRow(vector<vector<int>>& mat, vector<int> &chose, int n, int m) {\n        int cnt = 0;\n        \n        for(int i = 0; i < n; i++) {\n            bool ok = 1;\n            for(int j = 0; j < m; j++) {\n\t\t\t\t// If this cell in the ith row contains \'1\' but we haven\'t chosen this column, thus we cannot consider this row as covered\n                if(mat[i][j] == 1 && chose[j] == 0) {\n\t\t\t\t\tok = 0;\n\t\t\t\t\tbreak;\n\t\t\t\t}\n            }\n            if(ok) cnt++;\n        }\n        \n        return cnt;\n    }\n    \npublic:\n    int maximumRows(vector<vector<int>>& mat, int cols) {\n        ans = 0;\n        int n = mat.size(), m = mat[0].size();\n        vector<int> chose(m, 0); // to track the chosen columns \n        helper(mat, chose, 0, n, m, cols);\n        return ans;\n    }\n};\n```\n\nN = rows, M = columns\n\nTC: O(N * M * 2^M)\nSC: O(M * 2 ^ M)
['Backtracking', 'Recursion', 'C']