[C++] DFS + backtracking | Added comments to archit91's solution
Note: I have described the isValid() function with comments, and that is the main part for understanding this problem. \nBasically we are trying to create a con
**Note:** I have described the isValid() function with comments, and that is the main part for understanding this problem. \nBasically we are trying to create a configuration in cur of good or bad people by trying out all ways, then we are checking what we made is in accordance with what these people said (what good people said) is true or not. This part is described further in isValid().\n\n**Why is it backtracking** - Backtracking means to try out all possible ways, hence I think backtracking is correct word to describe what we are doing.\n\n**Time and space complexity**\n**T.C:** O(2^n * n^2) -\n-> 2^n - Create all possible combinations of size n.\n-> n^2 - Check validity of 2^n combinations each time by going through statements of all good persons (goodPersons == n persons in worst case leading to n^2).\n\n**S.C:** O(n) - Storing cur of size n.\n\n```\nclass Solution {\npublic:\n    int result = 0;\n    int n = 0;\n    int maximumGood(vector<vector<int>>& statements) {\n        n = statements.size();\n        string cur = "";\n        dfs(statements, cur, 0, 0);\n        return result;\n    }\n    \n    void dfs(vector<vector<int>>& statements, string& cur, int index, int goodPersonCount){\n        if(index == n){\n            //Check if cur is valid\n            if(isValid(cur, statements)) result = max(goodPersonCount, result);\n            return;\n        }\n        \n        //Make current person a good person and call DFS\n        cur.push_back(\'1\');\n        dfs(statements, cur, index+1, goodPersonCount+1);\n        \n        //Backtrack: Make current person a bad person and call DFS\n        cur.back() = \'0\';\n        dfs(statements, cur, index+1, goodPersonCount);\n        \n        cur.pop_back();\n    }\n    \n    bool isValid(string& cur, vector<vector<int>>& statements){\n        //isValid() will check if the statement of goodPerson (i) about person (j) i.e. statement[i][j], is contradictory to what we have in cur[j]\n        \n        //If it is contradictory, then in terms of question i is lying, and is not a goodPerson, so this is not a valid count.\n        \n        //If s[i][j] == 2, i.e. person i said nothing about j, then we can skip it.\n        for(int i=0; i<n; i++){\n            if(cur[i] == \'1\'){ //We only care about what good people say\n                //Now we check what they said is in accordance with what we have in cur\n                for(int j=0; j<n; j++){\n                    if(statements[i][j] != 2 && statements[i][j] != cur[j] - \'0\') return false;\n                }\n            }\n        }\n        \n        //All statements made by good person is in accordance with cur, so we have a valid count of good people\n        return true;\n    }\n};\n```
['Backtracking', 'Depth-First Search', 'C', 'C++']