C++ Brute force DFS
See my latest update in repo LeetCode\n\n## Solution 1. Brute Force (DFS)\n\nThe brute force solution is generating all the permuntations of the mentors and cal
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. Brute Force (DFS)\n\nThe brute force solution is generating all the permuntations of the mentors and calculate the score of this permutation and the students.\n\nThe permutation generation process with DFS takes `O(M! * M)` time and calculating the score takes `O(N)` time, so the overall time complexity is `O(M! * MN)`.\n\nSince `M` and `N` are at most `8` and `8! * 8^2 = 2,580,480 ~= 2.6e6`, such solution should be able to pass.\n\n```cpp\n// OJ: https://leetcode.com/contest/weekly-contest-251/problems/maximum-compatibility-score-sum/\n// Author: github.com/lzl124631x\n// Time: O(M! * MN)\n// Space: O(N)\nclass Solution {\n    int used[9] = {}, ans = 0, m, n;\n    void dfs(vector<vector<int>>& S, vector<vector<int>>& M, int i, int score) {\n        if (i == m) {\n            ans = max(ans, score);\n            return;\n        }\n        for (int j = 0; j < m; ++j) {\n            if (used[j]) continue;\n            used[j] = 1;\n            int s = 0;\n            for (int k = 0; k < n; ++k) s += S[i][k] == M[j][k]; // calculate the compatibility score of student `i` and mentor `j`.\n            dfs(S, M, i + 1, score + s);\n            used[j] = 0;\n        }\n    }\npublic:\n    int maxCompatibilitySum(vector<vector<int>>& S, vector<vector<int>>& M) {\n        m = S.size(), n = S[0].size();\n        dfs(S, M, 0, 0);\n        return ans;\n    }\n};\n```
[]