Backtracking explanation
Idea with the backtracking solution is to iterate over all candidates, and check for contradictions.\n\nFor each candidate we can assume they are either good or
Idea with the backtracking solution is to iterate over all candidates, and check for contradictions.\n\nFor each candidate we can assume they are either good or bad.\n\nIf they are good:\n* if they make a statement about any previously seen candidate that statement must be true (i.e. that the candidate is good/bad)\n* no previously seen good candidate states the current is bad\n\nIf they are bad:\n* if a previously seen good candidate states they are good, then that previous candidate cannot be good\n\nWe check for these conditions and prune branches when contradictions are found.\n\n```\nclass Solution:\n    def maximumGood(self, statements: List[List[int]]) -> int:\n        n = len(statements)\n        self.ans = 0\n\t\t# good candidate set for O(1) lookup\n        good = set()\n        \n        def backtracking(idx, count):\n            if idx == n:\n\t\t\t\t# found a potential solution\n                self.ans = max(self.ans, count)\n                return\n            \n            # assume idx is good\n            good.add(idx)\n            for i in range(idx):\n\t\t\t\t# check for any contradictions with previous assumptions\n                if (statements[idx][i] == 1 and i not in good) or (statements[idx][i] == 0 and i in good) or (i in good and statements[i][idx] == 0):\n                    break\n            else:\n\t\t\t\t# if no contradiction found then we can assume idx is good and continue search\n                backtracking(idx + 1, count + 1)\n            good.remove(idx)\n            \n            # assume idx is bad\n            for i in range(idx):\n\t\t\t\t# check for any contradictions with previous candidates thought to be good\n                if (i in good and statements[i][idx] == 1):\n\t\t\t\t\t# contradiction so prune current branch\n                    return\n            backtracking(idx + 1, count)\n    \n        backtracking(0, 0)\n        return self.ans\n```
['Backtracking', 'Python', 'Python3']