C++ solution using backtracking DFS
We can use DFS with backtracking to fetch all the valid combinations for this problem that would be C(m, cols) = m! / ((m - cols)! * cols!) here C denotes Combi
We can use **DFS** with **backtracking** to fetch all the **valid combinations** for this problem that would be C(m, cols) = m! / ((m - cols)! * cols!) here C denotes Combination or Binomial Coefficient and m denotes number of columns. Then we calculate the answer for each valid combination and return the maximum of all the valid answers. \n\nThis DFS trick can also be used to find all the premutations too. I saw this trick first used in an atcoder contest by tourist. I have mentioned that problem below this along with tourist\'s solution and editorial.\n\n**Similar Problem**\nProblem Link: https://atcoder.jp/contests/abc236/tasks/abc236_d\nTourist\'s Solution: https://atcoder.jp/contests/abc236/submissions/28725135\nEditorial: https://atcoder.jp/contests/abc236/editorial/3304\n\n**Note:** Learn to use lambda funtions if you code in C++ it makes your code many time easier to type then passing all the values by referance. References: https://usaco.guide/general/lambda-funcs?lang=cpp https://codeforces.com/blog/entry/89790.\n\n**Solution:**\n```Cpp\nclass Solution {\npublic:\n    int maximumRows(vector<vector<int>>& mat, int cols) {\n        const int n = (int)mat.size(), m = (int)mat[0].size();\n        int ans = 0;\n        vector<bool> vis(m, false);\n        function<void(int, int)> dfs = [&](int u, int cnt) -> void {\n            if(cnt == cols) {\n                int cur = 0;\n                for(int i = 0; i < n; i++) {\n                    bool flag = true;\n                    for(int j = 0; j < m; j++) {\n                        if(!vis[j] and mat[i][j]) flag = false;\n                        if(!flag) break;\n                    }\n                    cur += flag;\n                }\n                ans = max(ans, cur);\n            } else {\n                for(int i = u + 1; i < m; i++) {\n                    vis[i] = true;\n                    dfs(i, cnt + 1);\n                    vis[i] = false;\n                }\n            }\n        };\n        dfs(-1, 0);\n        return ans;\n    }\n};
['Backtracking', 'Depth-First Search', 'C']