Gray Code

Problem: Gray Code

To generate gray code regularly, we need to observe the example more carefully. We can found that the result of n as 1 is definitely [0, 1]. When n is two, it's clear that adding 0 can produce [00, 01], which is a group of gray code. Similarly we can generate [10, 11] by adding 1. The problem lies in how to combine these two groups together. We can see that [01, 11] is a pair of gray code since the only difference bit is which we add. This means, we can simply reverse the result of adding 1 and combine it with the result of adding 0. Don't forget that what we want is a list of decimal numbers, thus we need to change adding 1 to adding power of 2.

Code in Python:

class Solution(object):
    def grayCode1(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if n == 0:
            return [0]
        inners = self.grayCode(n-1)
        l = [inner for inner in inners]
        r = [int(pow(2, n-1)) + inner for inner in inners[::-1]]
        return l + r

However, recursion always occupies more space and running time. If we can do backtracking without recursion, we can run our code faster. It's clear that adding 0 don't change the value of number, and adding power of 2 is equal to using or operation between the origin and a bit-wise number with opening 1 and all zeros. Thus, we can use the former result and adding numbers based on reversed original result.

Code in Python:

class Solution(object):
    def grayCode(self, n):
        res = [0]
        for i in xrange(n):
            for j in xrange(len(res)-1, -1, -1):
                res.append(1 << i | res[j])
        return res