C++ | Faster than 100% |  Backtracking and Bit Mask | Comments Added
We calculate compatibility between every student and mentor. Since the number of mentors and students are capped at 8, we can check every possible combination o
We calculate compatibility between every student and mentor. Since the number of mentors and students are capped at 8, we can check every possible combination of mentor and student. To keep a track of mentor assigned to student, we use bit masking.\n\nRefer to the code below for the above approach - \n\n```\nclass Solution {\npublic:\n    vector<vector<int>> v;\n    int n;\n    int res=0;\n    \n\t// function to calucate compatibility between two vectors.\n    int compat(vector<int> a, vector<int> b) {\n        int ans = 0;\n        for(int i=0 ; i<a.size() ; i++) {\n            if(a[i]==b[i]) ans++;\n        }\n        return ans;\n    }\n    \n    void check(int idx, int bits, int sum) {\n       // if all students have been assinged a mentor, check whether resultant sum is maximum.\n\t   if(idx==n) {\n            res = max(res,sum);\n        }\n        \n        for(int i=0 ; i<n ; i++) {\n            // select an unassigned mentor \n\t\t\tif(bits & 1<<i) {\n\t\t\t    // mark mentor as assigned\n                bits = (bits ^ (1<<i));\n                sum = sum + v[idx][i];\n                // recur for next student\n\t\t\t\tcheck(idx+1,bits,sum);\n\t\t\t\t// backtrack\n                sum = sum - v[idx][i];\n                bits = bits | 1<<i;\n            }\n        }\n    }\n    \n    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {\n        vector<vector<int>> temp (8, vector<int> (8,0));\n        v = temp;\n        n = students.size();\n        \n\t\t// vector v store the compatibility between each student mentor pair.\n\t\tfor(int i=0 ; i<students.size() ; i++) {\n            for(int j=0 ; j<mentors.size() ; j++) {\n                v[i][j] = compat(students[i], mentors[j]);\n            }\n        }\n\t\t// the bit value is intialized at 255 as 255 = "11111111" in binary.\n        check(0,255,0);\n        return res;\n    }\n};\n```
[]