Efficient JS solution - Backtracking (Beat 100% time)
\n\nPro tip: Simply love Xi\xE8 \uD83D\uDC9C\nInstead of literally backtrack, using a binary representation of an interator is way faster. In addition, early re
![image.png](https://assets.leetcode.com/users/images/722780de-119e-498e-a30a-276cd66e19df_1706708555.364604.png)\n\nPro tip: Simply love Xi\xE8 \uD83D\uDC9C\nInstead of literally backtrack, using a binary representation of an interator is way faster. In addition, early return when we know even if a state is valid, it will not give more good people. Final addition, greedily iterate from $$2^n-1$$ down to $$0$$ instead of the opposite to hopefully get the answer with more bits (good people) sooner.\n\n# Complexity\n- Time complexity: $$O(2^n * n^2)$$\n- Space complexity: $$O(1)$$\n\n# Code\n```js\n/**\n * @param {number[][]} statements\n * @return {number}\n */\nvar maximumGood = function (statements) {\n  let n = statements.length;\n  let res = 0;\n\n  for (let i = (1 << n) - 1; i; --i) {\n    let flag = i;\n    let cnt = 0;\n    while (flag) {\n      cnt++;\n      flag -= flag & -flag;\n    }\n    if (cnt <= res) continue;\n\n    flag = 1;\n    for (let a = 0; a < n; ++a) {\n      if (i & (1 << a)) {\n        for (let b = 0; b < n; ++b) {\n          if (statements[a][b] != 2 && statements[a][b] != ((i >> b) & 1)) {\n            flag = 0;\n            break;\n          }\n        }\n        if (!flag) break;\n      }\n    }\n\n    if (flag) res = cnt;\n  }\n\n  return res;\n};\n```
['Backtracking', 'Greedy', 'JavaScript']