O(n * 2^n) backtracking approach? Beats 100% time
\nclass Solution {\npublic:\n    int maximumGood(vector<vector<int>>& statements) {\n        \n        vector<int> goodstates(statements.size(), 0);\n        ve
```\nclass Solution {\npublic:\n    int maximumGood(vector<vector<int>>& statements) {\n        \n        vector<int> goodstates(statements.size(), 0);\n        vector<int> badstates(statements.size(), 0);\n        \n        for(int i = 0; i < statements.size(); i++) {\n            for (int j = 0; j < statements.size(); j++) {\n                if (statements[i][j] == 0) {\n                    \n                    badstates[i] |= (1 << j);\n                    \n                } else if (statements[i][j] == 1) {\n                    \n                    goodstates[i] |= (1 << j);\n                    \n                }\n            }\n           \n        }\n        \n        int best = 0;\n        \n        backtrack(goodstates, badstates, 0, 0, 0, 0, best);\n        \n        return best;\n        \n    }\n    \n    void backtrack(vector<int>& goodstates, vector<int>& badstates, int person, int good, int bad, int current, int& best) {\n        \n        if (person == goodstates.size()) {\n            best = max(best, current);\n            return;\n        }\n        \n        bool goodperson = (good & (1 << person)) >> person;\n        \n        bool badperson = (bad & (1 << person)) >> person;\n        \n        \n        if (badperson || !goodperson) backtrack(goodstates, badstates, person+1, good, bad | (1 << person), current, best);\n        \n        if (goodperson || !badperson) {\n            \n            if ((badstates[person] & good)) return;\n            if ((goodstates[person] & bad)) return;\n            \n            backtrack(goodstates, badstates, person+1, good | goodstates[person] | (1 << person), bad | badstates[person], current+1, best);\n            \n        }\n        \n    }\n};\n```\n\nWould appreciate any input on if this is actually O(n * 2^n) or not. Essentially backtracking, but instead of checking if a given set is valid at the end, we only enter branches that do not cause logical contradictions.\n\nWe maintain ongoing sets of people marked "good" and people marked "bad" so far, and check for the following conditions:\n\nIf the current person is in the bad set, we skip them over. (If the current person is not in either set, we also try skipping them over, and add them to the bad set).\n\nIf the current person is in the good set (or not in either), we check for further contradictions before continuing:\n\nIf the current person\'s set of bad people and the current overall set of good people has any intersections, we end the branch.\n\nIf the current person\'s set of good people and the current overall set of bad people has any intersections, we end the branch.\n\nOtherwise, we can enter this as a valid branch, adding the current person\'s good and bad sets to the ongoing good and bad sets, and adding the current person to the good set if they were unmarked.\n\n\nThis guarantees that if we make it to the end of any branch, it will be valid, and cuts down on invalid branches. I implement all of these checks using & and | bit logic, which should be O(n), and I think if the backtracking itself is O(2^n) and the backtracking body is O(n) then the overall complexity is O(n * 2^n).  I hope the logic makes sense, let me know if any clarifications are needed.
[]