[Python] DFS Straightforward, Easy-Thinking, Explained
General Idea\n\nLet persons be an array of 0s and 1s, where persons[i] indicates the assumption we made towards person i (0 - bad, 1 - good).\n\nWe first create
### General Idea\n\nLet `persons` be an array of `0`s and `1`s, where `persons[i]` indicates the assumption we made towards person `i` (`0` - bad, `1` - good).\n\nWe first create a function `hasContradiction()` which determines if there is a contradiction exists in the `statements` array, if we assume the trustability to be `persons`. By observation, we can see that\n\n> there exists a contradiction if and only if an assumed good person states another assumed good person to be bad\n\nNext we want to create all the combinations of `persons`, we can achieve this by using DFS. Starting from an empty array, each step we recursivly append either a good or bad into our accumulative array, representing in one branch we assume the current person to be good, and in the other we assume it to be bad (visually, the process will be like growing a binary tree). We stop when the length of the array reaches `N` which is the total number of persons.\n\nThen if we iterate through all these possible combinations, and count the number of good person in them if the combination does not have a contradiction, by finding the maximal among them we will obtain our final answer.\n\n### Code\n\n```\nclass Solution:\n    def maximumGood(self, statements: List[List[int]]) -> int:\n        BAD, GOOD, NO_STATEMENT = 0, 1, 2\n        N = len(statements)\n        \n        def hasContradiction(persons):\n            for i in range(N):\n                for j in range(N):\n                    if statements[i][j] == NO_STATEMENT:\n                        continue\n                    if persons[i] == GOOD:\n                        if statements[i][j] != persons[j]:\n                            return True\n            return False\n        \n        ans = 0\n        def dfs(persons):\n            nonlocal ans\n            if len(persons) == N:\n                if not hasContradiction(persons):\n                    ans = max(ans, persons.count(GOOD))\n            else:\n                dfs(persons+[GOOD])\n                dfs(persons+[BAD])\n                \n        dfs([])\n        return ans\n```\n\n### Complexity Analysis\n- Time complexity: `O(2^N * N^2)`\n\n\tSince there are a total of `2^N` possible combinations of `persons`, and in each of these combinations we are performing `O(N^2)` operation to exam if there is a contradiction, the time complexity is `O(2^N * N^2)`\n- Space complexity: `O(N)`\n\n\tSInce we are using DFS to find all the possible combinations of the `persons` array, at each time we are storing a complete `0` to `N` array in the memory stack, this takes `O(N)` space\n\t\n
['Depth-First Search', 'Python']