Maximum Good People Based on Statements LeetCode solution in C++

1
class Solution {
2
 public:
3
  int result = 0;
4
  int n = 0;
5
  int maximumGood(vector<vector<int>> &statements) {
6
    n = statements.size();
7
    string cur = "";
8
    dfs(statements, cur, 0, 0);
9
    return result;
10
  }
11

12
  void dfs(vector<vector<int>> &statements, string &cur, int index, int goodPersonCount) {
13
    if (index == n) {
14
      // Check if cur is valid
15
      if (isValid(cur, statements)) result = max(goodPersonCount, result);
16
      return;
17
    }
18

19
    // Make current person a good person and call DFS
20
    cur.push_back('1');
21
    dfs(statements, cur, index + 1, goodPersonCount + 1);
22

23
    // Backtrack: Make current person a bad person and call DFS
24
    cur.back() = '0';
25
    dfs(statements, cur, index + 1, goodPersonCount);
26

27
    cur.pop_back();
28
  }
29

30
  bool isValid(string &cur, vector<vector<int>> &statements) {
31
    // isValid() will check if the statement of goodPerson (i) about person (j)
32
    // i.e. statement[i][j], is contradictory to what we have in cur[j]
33

34
    // If it is contradictory, then in terms of question i is lying, and is not
35
    // a goodPerson, so this is not a valid count.
36

37
    // If s[i][j] == 2, i.e. person i said nothing about j, then we can skip it.
38
    for (int i = 0; i < n; i++) {
39
      if (cur[i] == '1') { // We only care about what good people say
40
        // Now we check what they said is in accordance with what we have in cur
41
        for (int j = 0; j < n; j++) {
42
          if (statements[i][j] != 2 && statements[i][j] != cur[j] - '0') return false;
43
        }
44
      }
45
    }
46

47
    // All statements made by good person is in accordance with cur, so we have
48
    // a valid count of good people
49
    return true;
50
  }
51
};