# 1947. Maximum Compatibility Score Sum

• Time: $O(m! \cdot mn)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 class Solution { public: int maxCompatibilitySum(vector>& students, vector>& mentors) { int ans = 0; dfs(students, mentors, 0, /*score=*/0, vector(students.size()), ans); return ans; } private: void dfs(const vector>& students, const vector>& mentors, int i, int scoreSum, vector&& used, int& ans) { if (i == students.size()) { ans = max(ans, scoreSum); return; } for (int j = 0; j < students.size(); ++j) { if (used[j]) continue; used[j] = true; // mentors[j] is used. dfs(students, mentors, i + 1, scoreSum + getScore(students[i], mentors[j]), move(used), ans); used[j] = false; } } int getScore(const vector& student, const vector& mentor) { int score = 0; for (int i = 0; i < student.size(); ++i) if (student[i] == mentor[i]) ++score; return score; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public int maxCompatibilitySum(int[][] students, int[][] mentors) { dfs(students, mentors, 0, /*score=*/0, new boolean[students.length]); return ans; } private int ans = 0; private void dfs(int[][] students, int[][] mentors, int i, int scoreSum, boolean[] used) { if (i == students.length) { ans = Math.max(ans, scoreSum); return; } for (int j = 0; j < students.length; ++j) { if (used[j]) continue; used[j] = true; // mentors[j] is used. dfs(students, mentors, i + 1, scoreSum + getScore(students[i], mentors[j]), used); used[j] = false; } } private int getScore(int[] student, int[] mentor) { int score = 0; for (int i = 0; i < student.length; ++i) if (student[i] == mentor[i]) ++score; return score; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution: def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int: ans = 0 def dfs(i: int, scoreSum: int, used: List[bool]) -> None: nonlocal ans if i == len(students): ans = max(ans, scoreSum) return for j, mentor in enumerate(mentors): if used[j]: continue used[j] = True # mentors[j] is used. dfs(i + 1, scoreSum + sum(s == m for s, m in zip(students[i], mentor)), used) used[j] = False dfs(0, 0, [False] * len(students)) return ans