Maximum Compatibility Score Sum

The problem asks for an optimal pairing between students and mentors to maximize the total compatibility score. Since each of the m students must be paired with a unique mentor from the m available mentors, any valid pairing corresponds to a permutation of the mentors. The brute-force approach is to generate every possible permutation of mentors, calculate the total score for each permutation, and find the maximum among them. This can be implemented using a recursive backtracking algorithm that explores all possible assignments.

• Pre-computation: First, it's helpful to pre-compute the compatibility scores for every possible student-mentor pair and store them in an m x m matrix, let's call it scores. scores[i][j] will hold the score for student i and mentor j. This takes O(m*m*n) time.
• Backtracking Function: Define a recursive function, for example, backtrack(studentIndex, currentScore). This function will try to assign a mentor to studentIndex.
• State: The state of the recursion is defined by the studentIndex we are currently considering and the set of mentors who have already been assigned. We can use a boolean array, visitedMentors, to keep track of used mentors.
• Base Case: The recursion stops when studentIndex equals m, which means all students have been assigned a mentor. At this point, we compare the currentScore with a global maximum score and update it if the currentScore is higher.
• Recursive Step: For the current studentIndex, we iterate through all available mentors (j from 0 to m-1). If mentors[j] has not been visited:
  1. Mark mentors[j] as visited.
  2. Add the score scores[studentIndex][j] to currentScore.
  3. Make a recursive call for the next student: backtrack(studentIndex + 1, newCurrentScore).
  4. After the recursive call returns, we backtrack by un-marking mentors[j] as visited and subtracting the score. This allows us to explore other possible assignments for studentIndex.

This approach systematically explores every single possible assignment of students to mentors. We can think of this as building an assignment one student at a time.

class Solution {
    int maxScore = 0;

    public int maxCompatibilitySum(int[][] students, int[][] mentors) {
        int m = students.length;
        int n = students[0].length;
        
        // Pre-compute scores for all student-mentor pairs
        int[][] scores = new int[m][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                int score = 0;
                for (int k = 0; k < n; k++) {
                    if (students[i][k] == mentors[j][k]) {
                        score++;
                    }
                }
                scores[i][j] = score;
            }
        }

        boolean[] visitedMentors = new boolean[m];
        backtrack(0, 0, scores, visitedMentors);
        return maxScore;
    }

    private void backtrack(int studentIndex, int currentScore, int[][] scores, boolean[] visitedMentors) {
        int m = scores.length;
        if (studentIndex == m) {
            maxScore = Math.max(maxScore, currentScore);
            return;
        }

        // Iterate through all mentors for the current student
        for (int mentorIndex = 0; mentorIndex < m; mentorIndex++) {
            if (!visitedMentors[mentorIndex]) {
                // Choose
                visitedMentors[mentorIndex] = true;
                // Recurse
                backtrack(studentIndex + 1, currentScore + scores[studentIndex][mentorIndex], scores, visitedMentors);
                // Unchoose (Backtrack)
                visitedMentors[mentorIndex] = false;
            }
        }
    }
}