JAVA DFS + Memorization faster than 100%
\nclass Solution {\n    public int maxCompatibilitySum(int[][] students, int[][] mentors) {\n        int[][] scores = new int[students.length][students.length];
```\nclass Solution {\n    public int maxCompatibilitySum(int[][] students, int[][] mentors) {\n        int[][] scores = new int[students.length][students.length];\n        for (int i = 0; i < scores.length; i++) {\n            for (int j = 0; j < scores[0].length; j++) {\n                scores[i][j] = getCompatibilityScore(students[i], mentors[j]);\n            }\n        }\n        boolean[][] states = new boolean[2][students.length];\n\t\t// Use list of indexes to represent whethe current state has been visited or not\n        Map<List<Integer>, Integer> cache = new HashMap<>();\n        return getMaxScore(scores, cache, states);\n    }\n    \n    private int getMaxScore(int[][] scores, Map<List<Integer>, Integer> cache, boolean[][] states) {\n        List<Integer> indexes = getIndexes(states);\n\t\t// If visited, directly return\n        if (cache.containsKey(indexes)) {\n            return cache.get(indexes);\n        }\n        // there is only one element\n        if (indexes.size() == 2) {\n            cache.put(indexes, scores[indexes.get(0)][indexes.get(1)]);\n            return cache.get(indexes);\n        }\n        // there are a lot element\n        int currMax = 0;\n        for (int i = 0; i < indexes.size() / 2; i++) {\n            int row = indexes.get(0);\n            states[0][row] = true;\n            for (int j = 0; j < indexes.size() / 2; j++) {\n                int col = indexes.get(j + indexes.size() / 2);\n                states[1][col] = true;\n                currMax = Math.max(currMax, scores[row][col] + getMaxScore(scores, cache, states));\n                states[1][col] = false;\n            }\n            states[0][row] = false;\n        }\n        cache.put(indexes, currMax);\n        return cache.get(indexes);\n    }\n    \n    private List<Integer> getIndexes(boolean[][] states) {\n        List<Integer> indexes = new ArrayList<>();\n        for (int i = 0; i < states.length; i++) {\n            for (int j = 0; j < states[0].length; j++) {\n                if (states[i][j] == false) {\n                    indexes.add(j);\n                }\n            }\n        }\n        return indexes;\n    }\n    \n    private int getCompatibilityScore(int[] student, int[] mentor) {\n        int sum = 0;\n        for (int i = 0; i < student.length; i++) {\n            if (student[i] == mentor[i]) {\n                sum++;\n            }\n        }\n        return sum;\n    }\n}\n```
[]