Problem statement

https://leetcode.com/problems/gray-code/

Solution

The idea is to use recursion, if we have gray code for n-1, than we can construct gray code for n easily. Imagine, that n = 4 and we have code [0,1,3,2,6,7,5,4]. Then we need to add numbers in [8, 15]. Let us add 8 to each number, so we have [8, 9, 11, 10, 14, 15, 13, 12] which is also code with property that every two adjacent number differ by one bit. All we need to do is to concatenate these two lists, but first we need to invert one of them to get [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8].

Complexity

Time complexity is O(2^n), space as well.

Code

class Solution:
    def grayCode(self, n):
        if n == 0: return [0]
        t = self.grayCode(n-1)
        return t + [i+(1<<(n-1)) for i in t][::-1]