✅ [C++/Python] Simple Solution w/ Explanation | DFS+Backtracking and Bitmasking
We need to find maximum number of people who can be good in accordance with the given statements.\n\n---\n\n\u2714\uFE0F Solution - I (DFS + Backtrack)\n\nA per
We need to find maximum number of people who can be good in accordance with the given statements.\n\n---\n\n\u2714\uFE0F ***Solution - I (DFS + Backtrack)***\n\nA person can either be good or bad. \nHowever, we cant be sure & assigning a person as good cant lead to contradictions in statements\nWe explore both possibilities of a person being good or bad\nFinally, we check if current configuration is valid or not\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int n, ans = 0;\n    int maximumGood(vector<vector<int>>& S) {\n        n = size(S);\n        string cur = ""; cur.reserve(n);\n        dfs(S, cur, 0, 0);\n        return ans;\n    }\n    void dfs(vector<vector<int>>& S, string& cur, int i, int cnt) {\n        if(i == n) {\n\t\t\t// if valid, update ans to store maximum good person found till now\n            if(valid(S, cur)) ans = max(ans, cnt);\n            return;\n        }\n        cur.append(1, \'0\');\n        dfs(S, cur, i+1, cnt);        // assuming ith person is bad\n        cur.back() = \'1\';\n        dfs(S, cur, i+1, cnt + 1);    // assuming ith person is good\n        cur.pop_back();        \n    }\n    bool valid(vector<vector<int>>& S, string& cur) {\n        for(int i = 0; i < n; i++) \n            if(cur[i] == \'1\') \n                for(int j = 0; j < n; j++) \n                    if(S[i][j] != 2 && S[i][j] != cur[j] - \'0\') return false;\n        return true;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def maximumGood(self, S):\n        n, ans = len(S), 0\n        def valid(cur):\n            for i in range(n):\n                if cur[i]:\n                    for j in range(n):\n                        if S[i][j] != 2 and S[i][j] != cur[j]: return False\n            return True;\n        def dfs(cur, i, cnt):\n            nonlocal ans\n            if i == n:\n                if valid(cur): ans = max(ans, cnt)\n                return\n            cur.append(0)\n            dfs(cur, i+1, cnt)\n            cur[-1] = 1\n            dfs(cur, i+1, cnt+1)\n            cur.pop()\n        \n        dfs([], 0, 0)\n        return ans\n        \n```\n\n***Time Complexity :*** <code>O(N<sup>2</sup>*2<sup>N</sup>)</code>, where `N` is the number of people\n***Space Complexity :*** `O(N)`\n\n\n----\n\n\u2714\uFE0F ***Solution - II (Bitmasking)***\n\nThe same thing as above, but using bitmasking which should be more efficient than backtracking. We are basically exploring all possible configurations for given `n` people.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int maximumGood(vector<vector<int>>& S) {\n        int n = size(S), ans = 0;\n        auto valid = [&](int cur) {\n            for(int i = 0; i < n; i++)\n                if(cur & 1 << n-1-i)\n                    for(int j = 0; j < n; j++)\n                        if(S[i][j] != 2 && S[i][j] != bool(cur & 1 << n-1-j)) return false;\n            return true;\n        };\n        for(int i = 0; i < 1 << n; i++)                            // bits in i denotes person configuration\n            if(valid(i)) ans = max(ans, __builtin_popcount(i));    // update ans if valid config\n        return ans;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def maximumGood(self, S):\n        n, ans = len(S), 0\n        def valid(cur):\n            for i in range(n):\n                if cur & 1 << n-1-i:\n                    for j in range(n):\n                        if S[i][j] != 2 and S[i][j] != bool(cur & 1 << n-1-j): return False\n            return True\n        return max(bin(i).count(\'1\') if valid(i) else 0 for i in range(1 << n))\n```\n\n***Time Complexity :*** <code>O(N<sup>2</sup>*2<sup>N</sup>)</code>, where `N` is the number of people\n***Space Complexity :*** `O(1)`\n\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---
[]