[Python3, Java, C++] Subsets O(n^2 * 2^n)
I recommend checking this problem first: https://leetcode.com/problems/subsets/solution/\nLook for Approach 3: Lexicographic (Binary Sorted) Subsets\n\n We are 
I recommend checking this problem first: https://leetcode.com/problems/subsets/solution/\nLook for *Approach 3: Lexicographic (Binary Sorted) Subsets*\n\n* We are going to generate every possible permutation of good and bad people\n* Then we check if this permutation satisfies the given constraints\n\nPermutation representation in binary:\n\n>111 : 0 -> good, 1 -> good, 2 -> good\n110 : 0 -> good, 1 -> good, 2 -> bad\n101 : 0 -> good, 1 -> bad, 2 -> good\n011 : 0 -> bad, 1 -> good, 2 -> good\n100 : 0 -> good, 1 -> bad, 2 -> bad\n... and so on.\n\nWith 3 people we will have 8 permutations(2<sup>n</sup>)\nWith 4 people we will have 16 permutations\n\n>For n = 3:\nLower limit: 1 << n = 2<sup>n</sup> = 8 = 1000\nUpper limit: 1 << (n + 1) - 1 = 2<sup>n+1</sup> - 1 = 16 - 1 = 15 = 1111\nInteger.toBinaryString(8).substring(1): 000\nInteger.toBinaryString(9).substring(1): 001\n...\nInteger.toBinaryString(15).substring(1): 111\n\nTo check if our permutation satisfies the constraints, we check if the statements of good people in our permutation are making any contradictions. If they are, this permutation will not hold and we can return false.\n\nIf our `permutation` satisfies the given constraints, count the number of ones in our `permutation`.\nPermutation with maximum ones is the answer. \n\n<iframe src="https://leetcode.com/playground/aSJnx2F5/shared" frameBorder="0" width="700" height="460"></iframe>\n\n*Time Complexity*: O(n<sup>2</sup> * 2<sup>n</sup>)\n
['C', 'Python', 'Java']