Maximum Compatibility Score Sum LeetCode solution in C++

1
class Solution {
2
  // Calculating compatibility scores of ith student and jth mentor
3
  int cal(int i, int j, vector<vector<int>> &arr1, vector<vector<int>> &arr2) {
4
    int cnt = 0;
5
    for (int k = 0; k < arr1[0].size(); k++) {
6
      if (arr1[i][k] == arr2[j][k]) {
7
        cnt++;
8
      }
9
    }
10
    return cnt;
11
  }
12

13
  int helper(int i, int m, vector<vector<int>> &arr1, vector<vector<int>> &arr2,
14
             vector<bool> &vis) {
15
    if (i == m) {
16
      return 0;
17
    }
18
    int ans = 0;
19
    for (int j = 0; j < m; j++) {
20
      if (!vis[j]) {
21
        vis[j] = 1;
22
        ans = max(ans, cal(i, j, arr1, arr2) + helper(i + 1, m, arr1, arr2, vis));
23
        vis[j] = 0; // Backtracking
24
      }
25
    }
26
    return ans;
27
  }
28

29
 public:
30
  int maxCompatibilitySum(vector<vector<int>> &students, vector<vector<int>> &mentors) {
31
    int m = students.size();
32
    vector<bool> vis(m,
33
                     0); // To keep track of which mentor is already paired up
34
    return helper(0, m, students, mentors, vis);
35
  }
36
};