C++ Bitmask Subset Traversal O(2^N * N^2)
See my latest update in repo LeetCode\n\n\n## Solution 1. Bitmask Subset Traversal\n\nEnumerate bitmask m from 1 to 2^N - 1. If the ith bit of m is 1/0, it mean
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n\n## Solution 1. Bitmask Subset Traversal\n\nEnumerate bitmask `m` from `1` to `2^N - 1`. If the `i`th bit of `m` is `1`/`0`, it means that person `i` is good/bad.\n\nWe can ignore bad persons\' statements because they can be either true or false. But good persons\' statements must be all correct.\n\nTo test if this bitmask `m` is valid, we go through all the good persons\' statements and see if there is any contradiction.\n\n```cpp\n// OJ: https://leetcode.com/contest/weekly-contest-277/problems/maximum-good-people-based-on-statements/\n// Author: github.com/lzl124631x\n// Time: O(2^N * N^2)\n// Space: O(1)\nclass Solution {\npublic:\n    int maximumGood(vector<vector<int>>& A) {\n        int N = A.size(), ans = 0;\n        auto valid = [&](int m) {\n            for (int i = 0; i < N; ++i) {\n                if (m >> i & 1) { // person i is good\n                    for (int j = 0; j < N; ++j) { // test if there is any contradiction in the statements from person i\n                        int good = m >> j & 1; // whether person j is good\n                        if ((A[i][j] == 0 && good) || (A[i][j] == 1 && !good)) return false;\n                    }\n                }\n            }\n            return true;\n        };\n        for (int m = 1; m < (1 << N); ++m) {\n            if (valid(m)) ans = max(ans, __builtin_popcount(m));\n        }\n        return ans;\n    }\n};\n```
[]