Python 3 | Itertools & Bitmask | Explanation
Explanation\n- The idea is super simple: Test out possibilities and take the one has most good persons\n\t- There are at most 2^15 = 32768 possibilities\n\t- Th
### Explanation\n- The idea is super simple: Test out possibilities and take the one has most `good` persons\n\t- There are at most `2^15 = 32768` possibilities\n\t- The `n*n` matrix `statements` will have at most `15 * 15 = 225` cells\n\t- Total will be `2 ^ 15 * 15 * 15 = 7372800 ~= 7 * 10^3 * 10^3`\n\t\t- The general acceptance time complexity for LeetCode is around `10^6`\n\t\t- With some optimization, we can make the time complexity of the idea much faster than `7 * 10^3 * 10^3`\n### Approach \\#1. Use Python `itertools.product` to create mask\n- Use `itertools.product` to make a list only contains `0` or `1` with a length of `n = len(statements)`\n- Take this list and test it against the `statements` (i.e. `Proof by contradiction`)\n\t- Assuming the list is the correct `good` & `bad` identity for each person\n\t- If a `good` person\'s statement on someone else is different from what the list says, then there is a **contradiction**\n\t- We will discard this list and continue to test the next one\n- See below comments for more explanation\n```python\nclass Solution:\n    def maximumGood(self, statements: List[List[int]]) -> int:\n        ans, n = 0, len(statements)\n        for person in itertools.product([0, 1], repeat=n): # use itertools to create a list only contains 0 or 1\n            valid = True                                   # initially, we think the `person` list is valid\n            for i in range(n):\n                if not person[i]: continue                 # only `good` person\'s statement can lead to a contradiction, we don\'t care what `bad` person says\n                for j in range(n):\n                    if statements[i][j] == 2: continue     # ignore is no statement was made\n                    if statements[i][j] != person[j]:      # if there is a contradiction, then valid = False\n                        valid = False\n                        break                              # optimization: break the loop when not valid\n                if not valid:                              # optimization: break the loop when not valid\n                    break        \n            if valid: \n                ans = max(ans, sum(person))                # count sum only when valid == True\n        return ans\n```\n### Approach \\#2. Bitmask\n- Below is a bitmask version of the above approach. I think for most starters, **Approach #1** is easier to understand. If you are not familiar with bitmask or bit operation, that\'s totally fine. It takes time to build that mindset.\n- See comments below for more explanation\n```python\nclass Solution:\n    def maximumGood(self, statements: List[List[int]]) -> int:\n        ans, n = 0, len(statements)\n        for mask in range(1 << n):                           # 2**n possibilities\n            valid = True\n            for i in range(n):\n                if not (mask >> i) & 1: continue             # check if the `i`th person is a `good` person\n                for j in range(n):\n                    if statements[i][j] == 2: continue\n                    elif statements[i][j] != (mask >> j) & 1:# check if `i`th person\'s statement about `j` matches what `mask` says\n                        valid = False\n                        break                                # optimization: break the loop when not valid\n                if not valid: \n                    break                                    # optimization: break the loop when not valid\n            if valid: \n                ans = max(ans, bin(mask).count(\'1\'))         # count `1` in mask, take the largest\n        return ans\n```
['Bitmask', 'Python', 'Python3']