Python, brute force dfs/bitmask dp solution with explanation
backtrack (permutation)\nlist all permutation of student to enumearte all of student-teacher pairs.\n### python\npython\n\'\'\'\nPrecalculate the score for each
### backtrack (permutation)\nlist all permutation of student to enumearte all of student-teacher pairs.\n### python\n```python\n\'\'\'\nPrecalculate the score for each student-teacher pairing, and enumerate all of the pairing using permutation to find max score\ntc is O(n * (m^2) + m * m!), sc is O(m^2)\n\'\'\'\nclass Solution:\n    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n        backtrack = []\n        ans = 0\n        scores = [[0] * len(students) for _ in range(len(students))]\n        for i, vec_i in enumerate(students):\n            for j, vec_j in enumerate(mentors):\n                scores[i][j] = sum(x == y for x, y in zip(vec_i, vec_j))\n        def dfs(used_st):\n            if len(backtrack) == len(students):\n                nonlocal ans\n                ans = max(ans, sum(scores[backtrack[i]][i] for i in range(len(students))))\n                return\n            \n            for i in range(len(students)):\n                if used_st >> i & 1: continue\n                backtrack.append(i)\n                dfs(used_st | (1 << i))\n                backtrack.pop()\n        dfs(0)\n        return ans\n```\n\n### c++\n```cpp\nclass Solution {\npublic:\n    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {\n        int size = students.size();\n        vector<vector<int>> scores (size, vector<int>(size));\n        for (int i = 0; i < size; i+=1) {\n            for (int j = 0, sub; j < size; j+=1) {\n                sub = 0;\n                for (int k = 0; k < students[0].size(); k+=1)\n                    sub += (students[i][k] == mentors[j][k]);\n                scores[i][j] = sub;\n            }\n        }\n        vector<int> backtrack;\n        int ans = 0;\n        function<void(int)> dfs = [&] (int used) {\n            if (backtrack.size() == size) {\n                int sub = 0;\n                for (int i = 0; i < size; i+=1)\n                    sub += scores[backtrack[i]][i];\n                if (sub > ans) ans = sub;\n                return;\n            }\n            for (int i = 0; i < size; i+=1) {\n                if (used >> i & 1) continue;\n                backtrack.emplace_back(i);\n                dfs(used | (1 << i));\n                backtrack.pop_back();\n            }\n        };\n        dfs(0);\n        return ans;\n    }\n};\n```\n\n### bitmask dp\ndp[mask] is max score of matched some , a bit of 1 means a student is matched.\ncount how many matched student in mask = cnt,\nfor each matched students in mask,\nwe try to match cnt-th mentor with a matched student and calculate score.\n\ndp[mask] = max(dp[mask], dp[mask ^ (1 << j)] + scores[j][cnt-1]),\nwhere j is a matched student.\n\ntc is O(n * 2 ^n), sc is O(2^n + n* n).\n\n### python\n```python\nclass Solution:\n    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n        size = len(students)\n        scores = [[0] * size for _ in range(size)]\n        for i, vec_i in enumerate(students):\n            for j, vec_j in enumerate(mentors):\n                scores[i][j] = sum(x == y for x, y in zip(vec_i, vec_j))\n        dp = [0] * (1 << size)\n        for mask in range(1, 1 << size):\n            cnt = sum(mask >> j & 1 for j in range(size))\n            for j in range(size):\n                if mask >> j & 1:\n                    dp[mask] = max(dp[mask], dp[mask ^ (1 << j)] + scores[j][cnt-1])\n        return dp[(1 << size) - 1]\n```\n\n### c++\n```cpp\nclass Solution {\npublic:\n    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {\n        int size = students.size();\n        vector<vector<int>> scores (size, vector<int>(size));\n        for (int i = 0; i < size; i+=1) {\n            for (int j = 0, sub; j < size; j+=1) {\n                sub = 0;\n                for (int k = 0; k < students[0].size(); k+=1)\n                    sub += (students[i][k] == mentors[j][k]);\n                scores[i][j] = sub;\n            }\n        }\n        vector<int> dp (1 << size);\n        for (int mask = 1, cnt; mask < 1 << size; mask+=1) {\n            cnt = 0;\n            for (int j = 0; j < size; j+=1) cnt += mask >> j & 1;\n            for (int j = 0; j < size; j+=1) {\n                if (mask >> j & 1)\n                    dp[mask] = max(dp[mask], dp[mask ^ (1 << j)] + scores[j][cnt-1]);\n            }\n        }\n        return dp[(1 << size) - 1];\n    }\n};\n```
['Backtracking', 'C', 'Bitmask', 'Python']