Beats 76% on runtime [EXPLAINED]
Intuition\nFind the maximum number of "good" people in a group based on statements they make about each other. Each person either tells the truth or lies, so we
# Intuition\nFind the maximum number of "good" people in a group based on statements they make about each other. Each person either tells the truth or lies, so we must figure out the largest group of people where everyone can be consistent with their statements.\n\n# Approach\nRepresent each person as either "good" or "bad" using a bitmask, then check all possible subsets of people to see if their statements about each other are consistent, and track the maximum number of "good" people in valid subsets.\n\n# Complexity\n- Time complexity:\nO(2^n * n^2), where n is the number of people. We check all 2^n subsets and for each subset, we validate the statements, which takes up to n^2 time.\n\n- Space complexity:\n O(n^2), mainly for storing the statements matrix.\n\n# Code\n```python3 []\nclass Solution:\n    def maximumGood(self, statements: list[list[int]]) -> int:\n        n = len(statements)\n        max_good = 0\n        \n        # Iterate through all possible subsets (bitmasking)\n        for mask in range(1 << n):  # 1 << n is equivalent to 2^n\n            is_valid = True\n            good_people = 0\n            \n            # Check the validity of this subset (bitmask)\n            for i in range(n):\n                if (mask >> i) & 1:  # If person i is considered good\n                    good_people += 1\n                    # Check the statements made by person i\n                    for j in range(n):\n                        if statements[i][j] == 2:  # No statement about j\n                            continue\n                        elif statements[i][j] == 1:  # i says j is good\n                            if not ((mask >> j) & 1):  # j must be good\n                                is_valid = False\n                                break\n                        elif statements[i][j] == 0:  # i says j is bad\n                            if (mask >> j) & 1:  # j must be bad\n                                is_valid = False\n                                break\n                if not is_valid:\n                    break\n            \n            # If this subset is valid, update max_good\n            if is_valid:\n                max_good = max(max_good, good_people)\n        \n        return max_good\n\n```
['Array', 'Backtracking', 'Bit Manipulation', 'Enumeration', 'Bitmask', 'Python3']