Skip to content

1947. Maximum Compatibility Score Sum 👍

  • Time: $O(m! \cdot mn)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
 public:
  int maxCompatibilitySum(vector<vector<int>>& students,
                          vector<vector<int>>& mentors) {
    int ans = 0;
    dfs(students, mentors, 0, /*score=*/0, vector<bool>(students.size()), ans);
    return ans;
  }

 private:
  void dfs(const vector<vector<int>>& students,
           const vector<vector<int>>& mentors, int i, int scoreSum,
           vector<bool>&& used, int& ans) {
    if (i == students.size()) {
      ans = max(ans, scoreSum);
      return;
    }
    for (int j = 0; j < students.size(); ++j) {
      if (used[j])
        continue;
      used[j] = true;  // The `mentors[j]` is used.
      dfs(students, mentors, i + 1,
          scoreSum + getScore(students[i], mentors[j]), std::move(used), ans);
      used[j] = false;
    }
  }

  int getScore(const vector<int>& student, const vector<int>& mentor) {
    int score = 0;
    for (int i = 0; i < student.size(); ++i)
      if (student[i] == mentor[i])
        ++score;
    return score;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public int maxCompatibilitySum(int[][] students, int[][] mentors) {
    dfs(students, mentors, 0, /*score=*/0, new boolean[students.length]);
    return ans;
  }

  private int ans = 0;

  private void dfs(int[][] students, int[][] mentors, int i, int scoreSum, boolean[] used) {
    if (i == students.length) {
      ans = Math.max(ans, scoreSum);
      return;
    }
    for (int j = 0; j < students.length; ++j) {
      if (used[j])
        continue;
      used[j] = true; // The `mentors[j]` is used.
      dfs(students, mentors, i + 1, scoreSum + getScore(students[i], mentors[j]), used);
      used[j] = false;
    }
  }

  private int getScore(int[] student, int[] mentor) {
    int score = 0;
    for (int i = 0; i < student.length; ++i)
      if (student[i] == mentor[i])
        ++score;
    return score;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def maxCompatibilitySum(
      self,
      students: list[list[int]],
      mentors: list[list[int]],
  ) -> int:
    ans = 0

    def dfs(i: int, scoreSum: int, used: list[bool]) -> None:
      nonlocal ans
      if i == len(students):
        ans = max(ans, scoreSum)
        return

      for j, mentor in enumerate(mentors):
        if used[j]:
          continue
        used[j] = True  # The `mentors[j]` is used.
        dfs(i + 1, scoreSum + sum(s == m
                                  for s, m in zip(students[i], mentor)), used)
        used[j] = False

    dfs(0, 0, [False] * len(students))
    return ans