89. Gray Code

"""
89. Gray Code
这个Gray Code是有特点的， Gary Code 是按中线上下对称的。
0|00
0|01
  --- minor
0|11
0|10
----- minor
1|10
1|11
1|01
1|00

所以呢，在backtrack的时候要做一个copy然后把copy reverse 之后原始list每个值前面加0，copy list每个值前面加1。然后把两个list merge在一起调入下一层的递归。
"""

class Solution(object):
    def backtrack(self, n, n1, res):
        if n1 > n:
            return
        tmp = res[:]
        tmp.reverse()
        for i in range(0, len(res)):
            res[i] = "0" + res[i]
            tmp[i] = "1" + tmp[i]

        res.extend(tmp)

        self.backtrack(n, n1+1, res)
        return


    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if n == 0:
            return [0]

        res = ['0', '1']

        if n > 1:
            self.backtrack(n, 2, res)

        for i in range(0, len(res)):
            res[i] = int(res[i], 2)

        return res