题目如下：
n 位格雷码序列 是一个由 \(2^n\) 个整数组成的序列，其中：
每个整数都在范围 \([0, 2^n - 1]\) 内, 要求：
- 第一个整数是 0
- 一个整数在序列中出现 不超过一次
- 每对 相邻 整数的二进制表示 恰好一位不同 ，且
- 第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
说实话我一开始想的简单了，直接暴力搜索，最后发现不行，只能 refer 一下官方题解了
方法一
我们可以用归纳法，从 \(n-1\)推到\(n\)，设序列 \(G_n\) 为\(n\) 位的格雷码序列, 我们可以从 \(G_{n-1}\) 推到 \(G_n\)。
首先把 \(G_{n-1}\) 中所有元素的\(n-1\)位设为 1，得到\(G_{n-1}^T\), 然后拼接 \(G_{n-1}\)和\(G_{n-1}^T\)就得到了我们想要的结果。
为什么呢？其实很简单，\(G_{n-1}^T\) 中每个数字都与\(G_{n-1}\) 有且仅有一位不同, 且 \(G_{n-1}\)是\([0,2^{n-1}]\)的一个排列，\(G_{n-1}^T\)则是\([2^{n-1}, 2^{n}-1]\)上的排列。 二者组合后自然就得到了\([0,2^n-1]\)上的排列，且依次穿插后二进制位恰有一位不同。
方法二
这个方法是纯粹的找规律，如下： 