Hypothesize and Find Contradictions
This problem is pretty straightforward. Since there are only at most n = 15 people in the group, we can just create all 2^n possible lists of good people as hyp
This problem is pretty straightforward. Since there are only at most `n = 15` people in the group, we can just create all `2^n` possible lists of good people as hypotheses and check if there is a contadiction in each of the lists.\n\nThere are two possible contradictions. \n1. a good person thinks someone is bad, but that person is actually in the good list.\n2. a good person thinks someone is good but that person isn\'t actually in the good list.\n\nNote that because bad people may lie *or* tell the truth, they aren\'t useful at conveying information.\n\nHere is the code written in javascript:\n\n```js\nvar maximumGood = function(statements) {\n\n    // Accepts a list of good people and returns if there is no contradiction\n    function check(good) {\n        for (const p of good) {\n            for (let j = 0; j < statements.length; j++) {\n                // if good person p thinks person j lied, but \n                // person j is good, we have a contradiction\n                if (statements[p][j] === 0) {\n                    if (good.includes(j)) return false;\n                }\n                // if good person p thinks person j is good, but \n                // person j is not good, we have a contradiction\n                if (statements[p][j] === 1) {\n                    if (!good.includes(j)) return false;\n                }\n            }\n        }\n        return true;\n    }\n    \n    // Tries every possible list of good people, and\n    // and returns the length of the largest one.\n    function getLargestValidList(i, good) {\n        if (i >= statements.length) {\n            return check(good) ? good.length : 0;\n        }\n\t\t\n\t\t// check list including i\n        good.push(i);\n        let res = getLargestValidList(i + 1, good);\n        good.pop();\n\t\t\n\t\t// check list not including i and return the larger of the two\n        return Math.max(res, getLargestValidList(i + 1, good));\n    }\n    return getLargestValidList(0, []);\n};\n```\n\nThe time complexity of this implementation is `O(2^n * n^3)`. Good thing n is small!
[]