Python 3: TC O(m 2**m), SC O(2**m): DFS+BT optimized to DFS+Caching
Intuition\n\n## Brute Force\n\nThe brute force answer to pretty much all "what\'s the best matching?" problems is to literally try all possible pairings, with D
# Intuition\n\n## Brute Force\n\nThe brute force answer to pretty much all "what\'s the best matching?" problems is to literally try all possible pairings, with DFS + backtracking. It works pretty well.\n\nDFS + backtracking is a very good technique to know really well. It shows up in a lot of problems. And learning it improves your command of recursion and stack entry/exit operations which makes you better at related algorithms too.\n\nThe complexity is\n* for student `0` we consider all mentors `j in 0..m-1`, `m` choices\n  * for student `1` we consider all mentors `j\' != j`, `m-1` choices\n    * for student `2` we consider all mentors `j\'\' != j, j\'`, `m-2` choices\n      * ... etc.\n\nAnd so the cost is `O(m!)` stack frames. Tack on another factor of `m` because we iterate through the `m` mentors to find the ones that are free. (this can be optimized, but it\'s a bit tricky, involves Yates-shuffle-like operation you have to invert, yikes) \n\n## Optimization: Identify and Cache Repeated Subproblems\n\nAt first glance it doesn\'t look like there are repeated subproblems.\n\nBut matching problems often do have repeated subproblems when we\'re maximizng a sum, or another operation that commutes.\n\nSuppose we match student `0` with mentor `0` at the top level of DFS+BT, and then match student `1` with mentor `1`. Then we\'ll find the best matches of students 2+ with mentors 2+.\n\nIn another DFS+BT branch we\'ll match student `0` with mentor `1`, and match student `1` with mentor `0`. Then we\'ll find the best matches of students 2+ with mentors 2+.\n\nSame subproblem! The shared problem is we just need the *sum* of compatibilities over students `i:` with each subset of remaining mentors `j`. Sum commutes so we don\'t care about the order. We can sum from students 0..m-1 as done in DFS+BT... or we can sum from the last student backward, getting the best answer for `i:` and some set of available mentors `avail` by\n* iterating through the mentors\n* if mentor `j` is availble, then the score could be `compats[i][j]` plus the best possible compatibility of `i+1:` with `avail - {j}`\n\nSo the way to optimize is to **DFS + caching, with arguments `i` and `avail` as a set of items.**\n\nWe can\'t hash sets in Python because sets are mutable, but there are two alternatives:\n* brute force: use a `frozenset`, designed for exactly this situation\n* clever: **use a bit set, aka an integer where the bit `1 << j` indicates if `j` is available**\n\n# Complexity\n- Time complexity: `O(m 2**m)`\n  - for DFS + caching we sum up the operations per stack frame across all stack frames we cache\n  - for `i==0` no mentors are taken yet, so there are `m choose 0` configurations of `avail`\n  - for `i==1`, one mentor is taken; there are `m choose 1` possible `avail` values\n  - for `i`, `i` mentors are taken with `m choose i` possible\n  - so the sum of cached states is `m choose 0 + m choose 1 + ... == 2**m`\n  - to compute each cached state, we iterate over the `m` mentors to see if they\'re available. Therefore it\'s `O(m * 2**m)`\n  - we can be a bit faster by iterating only over the set bits, so the work would be `O(m*(m choose 0) + (m-1)*(m choose 1) + (m-2)*(m choose 2) + ...)` ... which is still `O(m * 2**m)`\n    - the first half of those terms have a prefactor of at least `m/2`\n    - and the sum `(m choose 0) + .. + (m choose m//2)` is order half of `2**m` because the terms are symmetric, `m choose i == m choose (m-i)`\n    - so we have at least `O(m/2 * 2**(m-1))` operations\n    - that simplifies to `O(m * 2**m / 4) = O(m * 2**m)`\n\n- Space complexity: `O(2**m)`, which is the number of cached states (see above)\n\nThe sum of all subsets of `m` elements is `2**m`, a fact you can basically just memorize. Therefore most "cache the answer for each subset" has a memory complexity of `2**m` and a time complexity of at *least* `2**m`.\n\n# Code\n```\nclass Solution:\n    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:\n        # n questions, answers 0 or 1\n        # m students 0..m-1\n        # m mentors\n\n        # student and mentors answered same questions of length n\n\n        m = len(students)\n        n = len(students[0])\n\n        # compat between student i and mentor j: total indices where students[i] == mentors[j], i.e. num q\'s answered the same\n\n        # maximize the sum of compat. scores\n\n        # m,n  <= 8\n\n        # DFS + BT?\n\n        # wlog each student i gets matched with a mentor j\n\n        # accelerate a bit by precomputing the compatibilities\n        compats = [[0]*m for _ in range(m)]\n        for i in range(m):\n            for j in range(m):\n                compats[i][j] = sum(a == b for a, b in zip(students[i], mentors[j]))\n\n        # mentor_avail = [True]*m\n        # max_compat = 0 # TODO: early pruning\n        # def pair(i: int, compat: int):\n        #     nonlocal max_compat\n            \n        #     if i == m:\n        #         max_compat = max(max_compat, compat)\n        #     else:\n        #         for j in range(m):\n        #             if not mentor_avail[j]: continue\n\n        #             mentor_avail[j] = False\n        #             pair(i+1, compat + compats[i][j])\n        #             mentor_avail[j] = True\n\n        # def pair(0, 0)\n\n        # return max_avail\n\n        # complexity: worst case we try all m pairings for student 0\n        #  and for each, all m-1 pairings for student 1, etc.\n        #  for 8!\n\n        # better: we could record the max compatibility for students i: with a specific subset of mentors still available\n        #     because we just need the total compatibility, not the details of the matching once we\'re done\n        #\n        # 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\n        # and thus it\'s the sum of m choose i over all i, aka 2**m which is a lot better than m!\n\n        ALL = (1 << m) - 1\n        @cache\n        def maxCompat(i: int, avail: int) -> int:\n            if i == m: return 0\n\n            ans = 0\n            for j in range(m):\n                b = 1 << j\n                if avail & b:\n                    # mentor is available: get max score where we bind i to j and continue with i+1 and remaining mentors\n                    ans = max(ans, compats[i][j] + maxCompat(i+1, avail ^ b))\n\n            return ans\n\n        return maxCompat(0, ALL)\n```
['Python3']