Maximum Good People Based on Statements LeetCode solution in Python

1
class Solution:
2
    def maximumGood(self, S):
3
        n, ans = len(S), 0
4

5
        def valid(cur):
6
            for i in range(n):
7
                if cur[i]:
8
                    for j in range(n):
9
                        if S[i][j] != 2 and S[i][j] != cur[j]:
10
                            return False
11
            return True
12

13
        def dfs(cur, i, cnt):
14
            nonlocal ans
15
            if i == n:
16
                if valid(cur):
17
                    ans = max(ans, cnt)
18
                return
19
            cur.append(0)
20
            dfs(cur, i + 1, cnt)
21
            cur[-1] = 1
22
            dfs(cur, i + 1, cnt + 1)
23
            cur.pop()
24

25
        dfs([], 0, 0)
26
        return ans