### 题目

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note: For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

### 暴力回溯

#### 代码

public class Solution {
public List<Integer> grayCode(int n) {
if (n == 0) { return new ArrayList<Integer>(Arrays.asList(new Integer[]{0})); }
List<Integer> res = new ArrayList<>();
recursive(res,n,0);
return res;
}
public boolean recursive(List<Integer> res, int n, int num) {
if (res.size() == (int)Math.pow(2.0,(double)n)) { return true; }
if (res.contains(num)) { return false; }
for (int i = 0; i < n; i++) {
int variant = num ^ mask; // 逐位取补码
if (recursive(res,n,variant)) { return true; }
}
res.remove(res.size()-1); // 失败回退
return false;
}
}

### 自底向上的动态规划

[0]
[0, 1]
[0, 1, 3, 2]
[0, 1, 3, 2, 6, 7, 5, 4]
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]

0000
0001
0011
0010

n=3时，以n=2的最后一个0010对称展开，然后在第2位都变成1

0000 #
0001 ##
0011 ###
0010 ####
0110 ####
0111 ###
0101 ##
0100 #
|

#### 代码

public class Solution {
public List<Integer> grayCode(int n) {
if (n == 0) { return new ArrayList<Integer>(Arrays.asList(new Integer[]{0})); }
List<Integer> res = grayCode(n-1);