Formatted question description: https://leetcode.ca/all/1947.html
1947. Maximum Compatibility Score Sum
Level
Medium
Description
There is a survey that consists of n
questions where each question’s answer is either 0
(no) or 1
(yes).
The survey was given to m
students numbered from 0
to m  1
and m
mentors numbered from 0
to m  1
. The answers of the students are represented by a 2D integer array students
where students[i]
is an integer array that contains the answers of the ith
student (0indexed). The answers of the mentors are represented by a 2D integer array mentors
where mentors[j]
is an integer array that contains the answers of the jth
mentor (0indexed).
Each student will be assigned to one mentor, and each mentor will have one student assigned to them. The compatibility score of a studentmentor pair is the number of answers that are the same for both the student and the mentor.
 For example, if the student’s answers were
[1, 0, 1]
and the mentor’s answers were[0, 0, 1]
, then their compatibility score is 2 because only the second and the third answers are the same.
You are tasked with finding the optimal studentmentor pairings to maximize the sum of the compatibility scores.
Given students
and mentors
, return the maximum compatibility score sum that can be achieved.
Example 1:
Input: students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]]
Output: 8
Explanation: We assign students to mentors in the following way:
 student 0 to mentor 2 with a compatibility score of 3.
 student 1 to mentor 0 with a compatibility score of 2.
 student 2 to mentor 1 with a compatibility score of 3.
The compatibility score sum is 3 + 2 + 3 = 8.
Example 2:
Input: students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]]
Output: 0
Explanation: The compatibility score of any studentmentor pair is 0.
Constraints:
m == students.length == mentors.length
n == students[i].length == mentors[j].length
1 <= m, n <= 8
students[i][k]
is either0
or1
.mentors[j][k]
is either0
or1
.
Solution
Since both m
and n
do not exceed 8, each row in students
and mentors
can be considered as a binary representation and can be converted into an integer that does not exceed 255. After converting into integers, calculate the permutations of the m
rows. For each permutation, calculate the compatibility score sum using bitwise operation, and return the maximum compatibility score sum.

class Solution { public int maxCompatibilitySum(int[][] students, int[][] mentors) { int m = students.length, n = students[0].length; int[] studentsNums = new int[m]; int[] mentorsNums = new int[m]; for (int i = 0; i < m; i++) { studentsNums[i] = convertToNum(students[i]); mentorsNums[i] = convertToNum(mentors[i]); } int[] nums = new int[m]; for (int i = 0; i < m; i++) nums[i] = i; int maxSum = 0; List<List<Integer>> permutations = permute(nums); for (List<Integer> permutation : permutations) { int sum = 0; for (int i = 0; i < m; i++) sum += n  Integer.bitCount(studentsNums[i] ^ mentorsNums[permutation.get(i)]); maxSum = Math.max(maxSum, sum); } return maxSum; } public int convertToNum(int[] arr) { int num = 0; int length = arr.length; for (int i = 0; i < length; i++) num += arr[i] << i; return num; } public List<List<Integer>> permute(int[] nums) { int length = nums.length; List<List<Integer>> permutations = new ArrayList<List<Integer>>(); List<Integer> permutation = new ArrayList<Integer>(); for (int i = 0; i < length; i++) permutation.add(nums[i]); backtrack(length, permutations, 0, permutation); return permutations; } public void backtrack(int length, List<List<Integer>> permutations, int start, List<Integer> permutation) { if (start == length) permutations.add(new ArrayList<Integer>(permutation)); else { for (int i = start; i < length; i++) { Collections.swap(permutation, start, i); backtrack(length, permutations, start + 1, permutation); Collections.swap(permutation, start, i); } } } }

Todo

# 1947. Maximum Compatibility Score Sum # https://leetcode.com/problems/maximumcompatibilityscoresum/ class Solution: def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) > int: n = len(students) def dfs(i, used, score): if i == n: return score res = float(inf) for j, mentor in enumerate(mentors): if j in used: continue ss = sum(int(a == b) for a, b in zip(students[i], mentor)) used.add(j) score += ss res = max(res, dfs(i + 1, used, score)) used.remove(j) score = ss return res return dfs(0, set(), 0)