[C++] Backtracking
Intuition\n Describe your first thoughts on how to solve this problem. \n\nUsing backtracking.\n\nfor a col with index i, there are two decisions: choose it and
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nUsing backtracking.\n\nfor a col with index i, there are two decisions: choose it and not choose it.\n\nSo the decision tree is like: \n\n               " "\n            /      \\\n          " "      "0" \n         /   \\     /  \\\n       " "   "1" "0" "0 1"\n\nThe number within the " " represents the col index you have chosen.\n\n# Complexity\n- Time complexity: $O(2^{selectCols} * mn)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\ndfs takes $O(2^{selectCols}$, and to verify every leaves of decision tree taks $O(mn)$.\n\n- Space complexity: $O(n)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nstd::vector IsCovered takes $O(n)$ space(n is number of cols). And the recursion stack space is also $O(n)$.\n\n# Code\n```cpp []\nclass Solution {\n    int IsCovered(const vector<int> &row, const vector<bool>& selectCols) {\n        for (int i = 0; i < row.size(); ++i) {\n            if (row[i] == 1 && selectCols[i] == false) {\n                return 0;\n            }\n        }\n        return 1;\n    }\n\n    int CoveredNumber(const vector<vector<int>>& matrix, const vector<bool>& selectCols) {\n        int num = 0;\n        for (const auto &row : matrix) {\n            num += IsCovered(row, selectCols);\n        }\n        return num;\n    }\n\npublic:\n    int maximumRows(vector<vector<int>>& matrix, int numSelect) {\n        int row = matrix.size();\n        if (row == 0) {\n            return 0;\n        }\n        int col = matrix[0].size();\n        if (col == 0) {\n            return 0;\n        }\n\n        int have_choose = 0;\n        int max_rows = 0;\n        vector<bool> selectCols(col, false);\n\n        std::function<void(int)> dfs = [&](int i) {\n            if (have_choose == numSelect) {\n                int num = CoveredNumber(matrix, selectCols);\n                max_rows = std::max(max_rows, num);\n                return;\n            }\n            if (i == col) {\n                return;\n            }\n            dfs(i + 1);\n            selectCols[i] = true;\n            have_choose += 1;\n            dfs(i + 1);\n            selectCols[i] = false;\n            have_choose -= 1;\n        };\n\n        dfs(0);\n        return max_rows;\n    }\n};\n```
['C++']