Maximum Compatibility Score Sum: Optimal Assignment with Backtracking

You have m students and m mentors, each with answers to n binary questions. You need to assign each student to exactly one mentor (one-to-one) so that the total compatibility score is maximized. The compatibility score between a student and a mentor is the number of questions where they gave the same answer.

This is LeetCode 1947: Maximum Compatibility Score Sum, and it is a clean example of an assignment problem that can be solved with backtracking over permutations or optimized with bitmask DP. If you have worked through Permutations, the core technique will feel familiar. The twist is that instead of generating permutations as output, you are evaluating each permutation against a scoring function and keeping the maximum.

The problem

Given two 2D arrays students and mentors, both of size m x n, where each element is 0 or 1:

• The compatibility score of student i and mentor j is the number of indices k where students[i][k] == mentors[j][k].
• Assign each student to a unique mentor to maximize the sum of compatibility scores.

For example, with students = [[1,1,0],[1,0,1],[0,0,1]] and mentors = [[1,0,0],[0,0,1],[1,1,0]]:

The optimal assignment is S0 to M2 (score 3), S1 to M0 (score 2), and S2 to M1 (score 2), giving a total of 7.

The approach

The key observation is that assigning students to mentors is equivalent to finding a permutation of mentors. Student 0 gets mentor perm[0], student 1 gets mentor perm[1], and so on. The total score for a given permutation is the sum of score[i][perm[i]] for all i.

Backtracking approach: Generate all permutations of mentor indices. For each permutation, compute the total compatibility score and track the maximum. This works because m is at most 8 (given by the constraints), so there are at most 8! = 40320 permutations.

Bitmask DP optimization: Instead of generating full permutations, use a bitmask to represent which mentors have been assigned. For each student (processed in order), try assigning each unassigned mentor. The state is dp[mask], where mask is the set of mentors already used. This avoids redundant computation when different orderings lead to the same set of assigned mentors.

Both approaches start by precomputing the compatibility score for every student-mentor pair, which takes O(m^2 * n) time.

Visual walkthrough

Let's trace through all 3! = 6 permutations for our example and see which one wins.

Permutation [2, 0, 1] gives the maximum total of 7. The backtracking approach tries all permutations systematically, and the bitmask DP approach compresses overlapping subproblems into shared states.

The code

def maxCompatibilitySum(students, mentors):
    m = len(students)
    n = len(students[0])

    score = [[0] * m for _ in range(m)]
    for i in range(m):
        for j in range(m):
            for k in range(n):
                if students[i][k] == mentors[j][k]:
                    score[i][j] += 1

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

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

    backtrack(0, 0)
    return best[0]

The function starts by building a score matrix. score[i][j] holds the number of matching answers between student i and mentor j. This precomputation avoids recounting matches every time we evaluate an assignment.

The backtrack function processes students in order from index 0 to m - 1. For each student, it tries every mentor that has not been used yet. It marks the mentor as used, recurses to the next student with the updated total, and then unmarks the mentor (the classic choose-explore-unchoose pattern).

When student_idx reaches m, all students have been assigned. We compare the running total against the best seen so far and update if needed.

The used array tracks which mentors are currently assigned. This is equivalent to generating permutations of mentor indices, but we accumulate the score along the way instead of building the full permutation first.

Complexity analysis

The backtracking approach generates all m! permutations. For each permutation, the scoring is already precomputed, so each leaf costs O(1). The total work across all recursive calls is O(m!). The precomputation of the score matrix costs O(m^2 * n). Since m is at most 8, both approaches are well within time limits.

The bitmask DP approach has 2^m states. For each state, we try up to m mentors, and each transition is O(1) using the precomputed scores. The total is O(2^m * m), plus O(m^2 * n) for precomputation.

Building blocks

Precompute pairwise scores

Before searching over assignments, compute all m^2 compatibility scores upfront. This separates the "measuring" step from the "optimizing" step and keeps each recursive call constant-time.

Permutation via backtracking (choose-explore-unchoose)

The assignment problem reduces to finding the best permutation. The used array ensures each mentor is picked exactly once. This is the same skeleton as Permutations, with a scoring function layered on top.

Bitmask DP for subset enumeration

When the number of elements is small (here, m is at most 8), a bitmask can represent which elements have been selected. This compresses the permutation search into a DP over subsets, eliminating redundant work when different orderings reach the same subset of assigned mentors.

Edge cases

• m = 1: Only one student and one mentor. The answer is simply the number of matching answers between them.
• All identical answers: Every student and mentor has the same binary array. Every pairing scores n, and every assignment totals m * n.
• All zeros vs all ones: If students are all [0,0,...,0] and mentors are all [1,1,...,1], every compatibility score is 0 and the answer is 0.
• m = 8 (maximum): 8! = 40320 permutations. The backtracking approach handles this comfortably. The bitmask DP approach uses 2^8 = 256 states, which is even faster.

From understanding to recall

You see how the assignment problem maps to permutation search, and how precomputing pairwise scores keeps each evaluation fast. The backtracking version uses the same choose-explore-unchoose template you have seen in Permutations and N-Queens. The bitmask DP version compresses overlapping subproblems. But can you write either solution from scratch under time pressure?

Spaced repetition bridges that gap. You practice the permutation backtracking skeleton, the pairwise score precomputation, and the bitmask DP transition from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "maximize assignment score" and the structure flows out without hesitation.

Related posts

• Permutations - Core technique for generating all possible assignments
• Combination Sum - Another backtracking problem exploring valid combinations
• N-Queens - Classic backtracking with constraint checking