# 89. Gray Code

{% embed url="<https://leetcode.com/problems/gray-code/submissions/>" %}

原来是需要借助 gray code 的一些性质，参考[维基百科](https://zh.wikipedia.org/wiki/%E6%A0%BC%E9%9B%B7%E7%A0%81)：n位元的格雷码可以从n-1位元的格雷码以上下镜射后加上新位元的方式快速的得到，如下图所示一般。

![](https://1821609058-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M74fKaD-4PpYzUZfdEf%2F-M8JFzpNbCbKUlsvJMr2%2F-M8JK3fz5jX_xmC9pGA6%2Fimage.png?alt=media\&token=0ed0e4ca-1a69-48d9-ba9e-615763410935)

其实就是把 (n-1) 位的gray code逆序，前面加个1（换成十进制来看就是加了2^(n-1)）。

```python
class Solution:
    def grayCode(self, n):
        if n == 0: return [0]
        else:
            res = self.grayCode(n - 1)
            for i in range(len(res) - 1, -1, -1):
                res.append((2 ** (n - 1)) + res[i])
            return res
```
