Maximum Compatibility Score Sum

medium backtracking bitmask array

Problem

You are given two equal-sized lists of binary answer sheets: one row per student and one row per mentor, every row having the same number of yes/no answers. Pairing a student with a mentor scores one point for each question where their answers agree. Assign every student to a different mentor (a one-to-one matching) so the total agreement score across all pairs is as large as possible, and return that maximum total.

Inputstudents = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]]

Output8

Assign student 0 → mentor 2 (score 3), student 1 → mentor 0 (score 2), student 2 → mentor 1 (score 3). Total = 3 + 2 + 3 = 8, the best possible.

students (rows by ;, bits by ,)

mentors (rows by ;, bits by ,)

def max_compatibility_sum(students, mentors):
    m, n = len(students), len(students[0])
    score = [[0] * m for _ in range(m)]
    for i in range(m):
        for j in range(m):
            score[i][j] = sum(students[i][q] == mentors[j][q] for q in range(n))

    best = [0]
    used = [False] * m

    def dfs(i, total):
        if i == m:
            best[0] = max(best[0], total)
            return
        for j in range(m):
            if not used[j]:
                used[j] = True
                dfs(i + 1, total + score[i][j])
                used[j] = False

    dfs(0, 0)
    return best[0]

function maxCompatibilitySum(students, mentors) {
  const m = students.length, n = students[0].length;
  const score = Array.from({ length: m }, () => new Array(m).fill(0));
  for (let i = 0; i < m; i++)
    for (let j = 0; j < m; j++)
      for (let q = 0; q < n; q++)
        if (students[i][q] === mentors[j][q]) score[i][j]++;

  let best = 0;
  const used = new Array(m).fill(false);
  function dfs(i, total) {
    if (i === m) { best = Math.max(best, total); return; }
    for (let j = 0; j < m; j++) {
      if (!used[j]) {
        used[j] = true;
        dfs(i + 1, total + score[i][j]);
        used[j] = false;
      }
    }
  }
  dfs(0, 0);
  return best;
}

class Solution {
    int best;
    public int maxCompatibilitySum(int[][] students, int[][] mentors) {
        int m = students.length, n = students[0].length;
        int[][] score = new int[m][m];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                for (int q = 0; q < n; q++)
                    if (students[i][q] == mentors[j][q]) score[i][j]++;
        best = 0;
        dfs(score, new boolean[m], 0, 0, m);
        return best;
    }
    void dfs(int[][] score, boolean[] used, int i, int total, int m) {
        if (i == m) { best = Math.max(best, total); return; }
        for (int j = 0; j < m; j++) {
            if (!used[j]) {
                used[j] = true;
                dfs(score, used, i + 1, total + score[i][j], m);
                used[j] = false;
            }
        }
    }
}

int best;
void dfs(vector<vector<int>>& score, vector<bool>& used, int i, int total, int m) {
    if (i == m) { best = max(best, total); return; }
    for (int j = 0; j < m; j++) {
        if (!used[j]) {
            used[j] = true;
            dfs(score, used, i + 1, total + score[i][j], m);
            used[j] = false;
        }
    }
}
int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
    int m = students.size(), n = students[0].size();
    vector<vector<int>> score(m, vector<int>(m, 0));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            for (int q = 0; q < n; q++)
                if (students[i][q] == mentors[j][q]) score[i][j]++;
    best = 0;
    vector<bool> used(m, false);
    dfs(score, used, 0, 0, m);
    return best;
}

Explanation

Each student and each mentor filled in the same questionnaire with 0/1 answers. The compatibility of a student–mentor pair is simply how many questions they answered the same way. We must match every student with a distinct mentor and want the sum of these pair scores to be as large as possible.

First we precompute a small m × m table score[i][j] = how well student i agrees with mentor j. With that table the questionnaire bits no longer matter — the task becomes "pick one mentor per student, no mentor reused, maximise the summed scores," which is a classic assignment problem.

Because m is tiny (at most 8), we just try all matchings with backtracking. dfs(i, total) assigns student i to some still-unused mentor j, marks that mentor used, and recurses on student i + 1 with the running total + score[i][j]. After the recursive call returns we unmark the mentor (the backtracking undo) so the next branch can use it again.

When i reaches m every student is paired, so total is one complete matching's score; we keep the largest such total in best.

Example: with the score table rows [2,0,3], [2,2,1], [1,3,0], the matching student 0→mentor 2, student 1→mentor 0, student 2→mentor 1 yields 3 + 2 + 3 = 8, and no other matching beats it, so the answer is 8.

Time: O(m·m·n + m!) Space: O(m·m)