C++ | Simple recursive approach explanation
This post can be beneficial for someone who lacks confidence in solving recursive problems.\n\nBrute force approach:\nGiven n people, each person can either be 
This post can be beneficial for someone who lacks confidence in solving recursive problems.\n\n**Brute force approach:**\nGiven n people, each person can either be good or bad, so there are 2<sup>n</sup> combinations but each combination may not be valid. So, if we apply brute force and check if its valid or not and based on that calculate the maximum no of good people, the time complexity for should be O(2<sup>n</sup> * n<sup>2</sup>). For n = 15, the complexity is not too large and will work within the alloted time frame.\nSo, we are good to go with brute force approach and do not need backtracking to prune the recursion tree (although that will be faster than this approach).\n\nLet\'s look at the code.\nIn the function definition, vector v is used to store whether the person i is good or bad. In case `i` is good, `v[i] = 1`, otherwise 0. A better approach could have been bitmasking, where we could have used a string of length n and stored character `1` at index `i` if person `i` is good.\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> stm;\n    int n;\n\tint rf(vector<int> v, int i){\n\t\t\tif(i>=n){\n\t\t\t\t//check valid\n\t\t\t\tint cnt = 0;\n\t\t\t\tfor(int i=0; i<n; i++){\n\t\t\t\t\tif(v[i] == 1){\n\t\t\t\t\t\tcnt++;\n\t\t\t\t\t\tfor(int j=0; j<n; j++){\n\t\t\t\t\t\t\t// if not valid, return -1\n\t\t\t\t\t\t\tif(stm[i][j] == 1 && v[j] == 0) return -1;\n\t\t\t\t\t\t\tif(stm[i][j] == 0 && v[j] == 1) return -1;\n\t\t\t\t\t\t}\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\t// if valid, return good people count\n\t\t\t\treturn cnt;\n\t\t\t}\n\t\t\t// let person i be good\n\t\t\tv[i] = 1;\n\t\t\tint x = rf(v,i+1);\n\t\t\t\n\t\t\t// let person i be bad\n\t\t\tv[i] = 0;\n\t\t\tint y = rf(v, i+1);\n\t\t\t\n\t\t\treturn max({0,x,y});\n\t}\n\tint maximumGood(vector<vector<int>>& statements) {\n        n = statements.size();\n        stm = statements;\n        vector<int> v(n);\n        return rf(v,0);\n    }\n};\n```\n\n
['Recursion']