Exhaustive Search with Bitmasking O(2^n * n^2) (With Explanation)
cpp\nclass Solution {\npublic:\n\tint maximumGood(vector<vector<int>>& statements) {\n\t\tint n = statements.size();\n\t\tint maxGoodPeople = 0;\n\t\tint mask =
```cpp\nclass Solution {\npublic:\n\tint maximumGood(vector<vector<int>>& statements) {\n\t\tint n = statements.size();\n\t\tint maxGoodPeople = 0;\n\t\tint mask = (1 << n);\n\t\tfor (int currMask = 1; currMask < mask; currMask++) {\n\t\t\tif (isAllGoodPeople(statements, currMask)) {\n\t\t\t\tmaxGoodPeople = max(maxGoodPeople, __builtin_popcount(currMask));\n\t\t\t}\n\t\t}\n\t\treturn maxGoodPeople;\n\t}\n\n\tbool isAllGoodPeople(vector<vector<int>>& statements, int currMask) {\n\t\tfor (int i = 0; i < statements.size(); i++) {\n\t\t\tif (currMask & (1 << i)) { // check whether current person is good or not\n\t\t\t\t// if it\'s a good person check his credibility by checking\n\t\t\t\t// whether everyone he says good is actually good and everyone he says bad\n\t\t\t\t// are really bad person\n\t\t\t\tfor (int j = 0; j < statements.size(); j++) {\n\t\t\t\t\tbool isGoodPerson = (currMask & (1 << j)) ? 1 : 0;\n\t\t\t\t\tif ((isGoodPerson && statements[i][j] == 0) || (!isGoodPerson && statements[i][j] == 1)) {\n\t\t\t\t\t\t// isGoodPerson && statements[i][j] == 0 -> according to our mask j-th person is good\n\t\t\t\t\t\t// but our i-th guy says he is not. So our assumption about i-th guy being good might be wrong.\n\t\t\t\t\t\t// invlid mask\n\n\t\t\t\t\t\t// !isGoodPerson && statements[i][j] == 1 -> according to our mask j-th person is bad\n\t\t\t\t\t\t// but our i-th guy says he is good. So our assumption about i-th guy being good might be wrong.\n\t\t\t\t\t\t// invlid mask\n\t\t\t\t\t\treturn false;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\treturn true;\n\t}\n};\n```
[]