Unlock the Secret to Maximizing Compatibility Scores with This Genius Algorithm! 🚀🔥
IntuitionThe problem requires finding the best pairing between students and mentors to maximize the compatibility score.
Since the number of students/mentors is
# Intuition
The problem requires finding the best pairing between students and mentors to maximize the compatibility score.  
Since the number of students/mentors is small (≤ 8), we can use backtracking to explore all possible assignments efficiently.  

# Approach
1. Use backtracking to generate all permutations of student-to-mentor pairings.  
2. Calculate the compatibility score for each assignment by comparing corresponding answers.  
3. Keep track of the maximum compatibility score found.  
4. Recursively explore all possible assignments while marking mentors as used and backtracking.  

# Complexity
- Time complexity:  
Since we are generating all permutations of students to mentors, the worst case complexity is **O(n!)**.  
Each permutation takes **O(n²)** to compute the compatibility score, so the final complexity is **O(n! * n²)**.  

- Space complexity:  
**O(n)** for recursion depth in the worst case (n students).  
**O(n²)** for storing the input.  
Overall, **O(n²)**.

# Code
```cpp []
class Solution {
public:
    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
        int ans = 0;
        h(students,mentors,0,0,ans);
        return ans;
    }

private:
    void h(vector<vector<int>>& students, vector<vector<int>>& mentors,int i,int com,int& ans){
        if(i >= students.size()){
        // updating ans to the max compatibility score 
            ans = max(ans,com);
            return;
        }

        // checking compability of i'th student with each mentor
        for(int j = 0;j < mentors.size();j++){
            // cout << com << " ";
            if(mentors[j].size()){
                int c = compatibility(i,j, students,mentors);
                vector<int> temp = mentors[j];
                mentors[j] = {};
                h(students,mentors,i+1, com+c,ans);
                mentors[j] = temp; //  backtracking
            }
        }
    }
    // finding the compatibility score
    int compatibility(int i,int j,vector<vector<int>>& students, vector<vector<int>>& mentors){
        int count = 0;
        for(int x=0;x < students[i].size();x++){
            if(students[i][x] == mentors[j][x]) count++;
        }
        return count;
    }
};
```
['C++']