[C++] DP + Bitmask | 4ms
Time Complexity: O((2^n)*n*m)\n\n\n\nint dp[300];      //dp-array\nclass Solution {\npublic:\n    int solve(vector<int> &a, vector<int> &b, int i, int mask, int
Time Complexity: `O((2^n)*n*m)`\n\n```\n\nint dp[300];      //dp-array\nclass Solution {\npublic:\n    int solve(vector<int> &a, vector<int> &b, int i, int mask, int n, int m){\n        if(i>=n){\n            return 0;\n        }\n        if(dp[mask]!=-1){\n            return dp[mask];\n        }\n        int ans=0;\n        for(int k=0; k<n; k++){    //for each mentor\n            if((mask&(1<<k))){                     //check if mentor has not chosen yet\n                int new_mask=mask^(1<<k);\n                \n                int current_ans=0;\n                for(int x=0; x<m; x++){\n                    if((a[i]&(1<<x)) == (b[k]&(1<<x))){      //if xth bit of student and mentor is same, increase the answer\n                        current_ans++;\n                    }\n                }\n                ans=max(ans, current_ans + solve(a, b, i+1, new_mask, n, m) );\n            }\n        }\n        return dp[mask]=ans;\n    }\n    \n    int maxCompatibilitySum(vector<vector<int>>& s, vector<vector<int>>& mr){\n        int n = s.size();\n        int m = s[0].size();\n        vector<int> a, b;\n        //convert to decimal e.g. [1,1,0] = 6\n        for(auto v: s){                                //for students array\n            int x=0;\n            for(int i=0; i<m; i++){\n                x+=(v[i]<<((m-i)-1));\n            }\n            a.push_back(x);\n        }\n        \n        for(auto v: mr){                               //for mentor array\n            int x=0;\n            for(int i=0; i<m; i++){\n                x+=(v[i]<<((m-i)-1));\n            }\n            b.push_back(x);\n        }\n        \n        int mask = pow(2, n)-1;                          //all set bit   1 -> mentor not chosen, 0 -> mentor chosen\n        //initialise dp array with -1\n        for(int j=0; j<=mask; j++){\n            dp[j]=-1;\n        }\n        \n        return solve(a, b, 0, mask, n, m);\n    }\n};\n\n```\n\n*If you like the solution, please **Upvote** \uD83D\uDC4D!!*\n\n***Similar concept problem*** : [1879. Minimum XOR Sum of Two Arrays](https://leetcode.com/problems/minimum-xor-sum-of-two-arrays/discuss/1238778/c-bitmaskdp)
[]