0%

### 题目描述

An n-bit gray code sequence is a sequence of `2^n` integers where:

• Every integer is in the inclusive range `[0, 2^n - 1]`,
• The first integer is `0`,
• An integer appears no more than once in the sequence,
• The binary representation of every pair of adjacent integers differs by exactly one bit, and
• The binary representation of the first and last integers differs by exactly one bit.

Given an integer `n`, return any valid n-bit gray code sequence.

### 例子

#### 例子 1

Input:`n = 2`
Output:`[0,1,3,2]`
Explanation:
The binary representation of `[0,1,3,2]` is `[00,01,11,10]`.

• `00` and `01` differ by one bit
• `01` and `11` differ by one bit
• `11` and `10` differ by one bit
• `10` and `00` differ by one bit
`[0,2,3,1]` is also a valid gray code sequence, whose binary representation is `[00,10,11,01]`.
• `00` and `10` differ by one bit
• `10` and `11` differ by one bit
• `11` and `01` differ by one bit
• `01` and `00` differ by one bit

#### 例子 2

Input:`n = 1`
Output:`[0,1]`

### Constraints

• `1 <= n <= 16`

### 解题思路

• `n = 2` 的第二组的后两个元素和前两个元素（除了最高位）互为镜像，区别是后两个元素的最高位是 `1`，可以看成是 `n = 1` 的答案后面从后往前遍历，并最高位加个1形成一组答案；
• `n = 2` 的第二组答案也是类似，区别是不是在最高位而是再低位加1

• 时间复杂度: `(2^n)`
• 空间复杂度: `(2^n)`

GitHub 代码同步地址： 89.GrayCode.cpp

GitHub: Leetcode-C++-Solution