[C++] OPTIMIZED Backtracking solution; Include Complexity Analysis; Beats 100%
\nint res;\n\nvoid backtracking(vector<vector<int>> &vec, int pos, vector<int> &visited, int count) {\n\tif (pos == vec.size()) {\n\t\tres = max(res, count);\n\
```\nint res;\n\nvoid backtracking(vector<vector<int>> &vec, int pos, vector<int> &visited, int count) {\n\tif (pos == vec.size()) {\n\t\tres = max(res, count);\n\t\treturn;\n\t}\n\tfor (int i = 0; i < vec.size() ; i++) {\n\t\tif (visited[i] == 1)\n\t\t\tcontinue;\n\t\tvisited[i] = 1;\n\t\tbacktracking(vec, pos + 1, visited, count + vec[pos][i]);\n\t\tvisited[i] = 0;\n\t}\n}\n\nint maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {\n\tres = 0;\n\tvector<vector<int>> sVec (students.size(), vector<int> (mentors.size(), 0));\n\tfor (int i = 0; i < students.size(); i++) {\n\t\tfor (int j = 0; j < mentors.size(); j++) {\n\t\t\tint score(0);    \n\t\t\tfor (int n = 0; n < students[0].size(); n++) {\n\t\t\t\tif (students[i][n] == mentors[j][n])\n\t\t\t\t\tscore++;\n\t\t\t}\n\t\t\tsVec[i][j] = score;\n\t\t}\n\t}\n\tvector<int> visited (mentors.size(), 0);\n\tbacktracking(sVec, 0, visited, 0);\n\treturn res;\n}\n```\n\t\nUsing backtracking to try out all the possibilities is intuitive. However, the total complexity and possibilities will be O(m! * n) \n(Imagine there are 4 students, 4 mentors and 2 questions. Student[0] can try 4 mentors; student[1] can try 3 mentors\u2026\u2026 And each pair takes O(n) to get the sum of compatibility score.)\n\n\n\n\nTherefore, we can generate a matrix of size m by m, called sVec.\nsVec[i][j] represents compatibility score of student[i] and mentor[j]. Using such a 2D vector, we could cut the backtracking time complexity to O(m!), because we don\u2019t have to iterate the n questions and calculate the score again. Calculate the matrix takes O(m*m*n); Backtracking takes O(m!). The final time complexity will be O(m*m*n + m!), which is equivalent to O(m!).\n\n
[]