[Java] My DFS + bitmask O(n * 2 ^ n) solution with tree pruning, beat 100% (1ms)
Share my O(n * 2 ^ n) time and O(1) space solution. Prunning the tree, optimizing space compleixity using bitmask.\n\n\nclass Solution {\n    private int maxRes
Share my O(n * 2 ^ n) time and O(1) space solution. Prunning the tree, optimizing space compleixity using bitmask.\n\n```\nclass Solution {\n    private int maxResult = 0;\n\n    public int maximumGood(int[][] statements) {\n        // Given 2 <= n <= 15, the states of all people can be stored in a bitmask (32 digits) \n        int bitmask = 0;\n        checkStateFrom(bitmask, 0, 0, statements);\n        return maxResult;\n    }\n    \n    private void checkStateFrom(int bitmask, int curr, int goodCount, int[][] statements) {\n        int n = statements.length;\n        \n        if (curr == statements.length) {\n            maxResult = Math.max(goodCount, maxResult);\n            return;\n        }\n        \n        // pruning useless branches\n        if (goodCount + n - curr <= maxResult) {\n            return;\n        }\n        \n        boolean canBeGood = true;\n        boolean canBeBad = true;\n\t\t// for each previous person, check if there\'s any contradictory statements\n        for (int i = 0; i < curr; i++) {\n            int iStatement = (bitmask >> i) % 2;\n            if (iStatement == 1 && statements[i][curr] == 0 /* Violates i\'s statement */\n               || statements[curr][i] != 2 && statements[curr][i] != iStatement) { /* Wrong statement about i */\n                canBeGood = false;\n            }\n            if (iStatement == 1 && statements[i][curr] == 1) { /* Violates i\'s statement */\n                canBeBad = false;\n            }\n            if (!canBeGood && !canBeBad) {\n                return;\n            }\n        }\n        if (canBeGood) {\n            checkStateFrom(bitmask + (1 << curr), curr + 1, goodCount + 1, statements);\n        }      \n        if (canBeBad) {\n            checkStateFrom(bitmask, curr + 1, goodCount, statements);\n        }\n        \n    }\n}\n```
['Bitmask', 'Java']