<p>There is a survey that consists of <code>n</code> questions where each question&#39;s answer is either <code>0</code> (no) or <code>1</code> (yes).</p>

<p>The survey was given to <code>m</code> students numbered from <code>0</code> to <code>m - 1</code> and <code>m</code> mentors numbered from <code>0</code> to <code>m - 1</code>. The answers of the students are represented by a 2D integer array <code>students</code> where <code>students[i]</code> is an integer array that contains the answers of the <code>i<sup>th</sup></code> student (<strong>0-indexed</strong>). The answers of the mentors are represented by a 2D integer array <code>mentors</code> where <code>mentors[j]</code> is an integer array that contains the answers of the <code>j<sup>th</sup></code> mentor (<strong>0-indexed</strong>).</p>

<p>Each student will be assigned to <strong>one</strong> mentor, and each mentor will have <strong>one</strong> student assigned to them. The <strong>compatibility score</strong> of a student-mentor pair is the number of answers that are the same for both the student and the mentor.</p>

<ul>
	<li>For example, if the student&#39;s answers were <code>[1, <u>0</u>, <u>1</u>]</code> and the mentor&#39;s answers were <code>[0, <u>0</u>, <u>1</u>]</code>, then their compatibility score is 2 because only the second and the third answers are the same.</li>
</ul>

<p>You are tasked with finding the optimal student-mentor pairings to <strong>maximize</strong> the<strong> sum of the compatibility scores</strong>.</p>

<p>Given <code>students</code> and <code>mentors</code>, return <em>the <strong>maximum compatibility score sum</strong> that can be achieved.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]]
<strong>Output:</strong> 8
<strong>Explanation:</strong>&nbsp;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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> The compatibility score of any student-mentor pair is 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == students.length == mentors.length</code></li>
	<li><code>n == students[i].length == mentors[j].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 8</code></li>
	<li><code>students[i][k]</code> is either <code>0</code> or <code>1</code>.</li>
	<li><code>mentors[j][k]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

class Solution:
    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
                # n questions, answers 0 or 1
        # m students 0..m-1
        # m mentors

        # student and mentors answered same questions of length n

        m = len(students)
        n = len(students[0])

        # compat between student i and mentor j: total indices where students[i] == mentors[j], i.e. num q's answered the same

        # maximize the sum of compat. scores

        # m,n  <= 8

        # DFS + BT?

        # wlog each student i gets matched with a mentor j

        # accelerate a bit by precomputing the compatibilities
        compats = [[0]*m for _ in range(m)]
        for i in range(m):
            for j in range(m):
                compats[i][j] = sum(a == b for a, b in zip(students[i], mentors[j]))

        # mentor_avail = [True]*m
        # max_compat = 0 # TODO: early pruning
        # def pair(i: int, compat: int):
        #     nonlocal max_compat
            
        #     if i == m:
        #         max_compat = max(max_compat, compat)
        #     else:
        #         for j in range(m):
        #             if not mentor_avail[j]: continue

        #             mentor_avail[j] = False
        #             pair(i+1, compat + compats[i][j])
        #             mentor_avail[j] = True

        # def pair(0, 0)

        # return max_avail

        # complexity: worst case we try all m pairings for student 0
        #  and for each, all m-1 pairings for student 1, etc.
        #  for 8!

        # better: we could record the max compatibility for students i: with a specific subset of mentors still available
        #     because we just need the total compatibility, not the details of the matching once we're done
        #
        # so for each i there would be m choose (m-i) == m choose i ways to have remaining items, only distinct subsets give different answers
        # and thus it's the sum of m choose i over all i, aka 2**m which is a lot better than m!

        ALL = (1 << m) - 1
        @cache
        def maxCompat(i: int, avail: int) -> int:
            if i == m: return 0

            ans = 0
            for j in range(m):
                b = 1 << j
                if avail & b:
                    # mentor is available: get max score where we bind i to j and continue with i+1 and remaining mentors
                    ans = max(ans, compats[i][j] + maxCompat(i+1, avail ^ b))

            return ans

        return maxCompat(0, ALL)

53