**Solution1. Simplified - Special thanks to @yuyibestman**

This is an iterative solution: Add prefix '1' to the previous sequence (from the last one). Because the the previous sequence should differ 1 bit between the successive two numbers, so if we add prefix '1' to them, they should still differ 1 bit between the successive two numbers.

```
There're two parts for sequence(i+1):
n = 2: 00(1), 01(2), 11(3), 10(4)
=> n = 3: 000(1), 011(2) 011(3) 010(4) - PART1
n = 3: 110(4), 111(3) 101(2) 100(1) - PART2
PART1: Same as sequence(i);
PART2: Add prefix '1' to the sequence(i) (from the last one).
```

**JAVA Code:**

```
public List<Integer> grayCode(int n) {
List<Integer>res = new LinkedList<Integer>();
res.add(0);
for (int i = 0; i < n; i++) {
int size = res.size();
for (int j = size - 1; j >= 0; j--) {// Add prefix '1' to the previous sequence (from the last one)
res.add(res.get(j) | (1 << i));
}
}
return res;
}
```

**Solution2. DFS**

The basic idea is using DFS to change 1 bit of the last visited number each time. It's a bit more complex than solution1, but it can output all possible sequences if we want. So, still worth a shot ;)

Changing 1 bit part is messed up, didn't figure out how to change 1 bit concisely, any advice would be appreciated!

**JAVA Code:**

```
public List<Integer> grayCode(int n) {
List<Integer> res = new LinkedList<Integer>();
res.add(0);
DFS(n, res);
return res;
}
boolean DFS(int n, List<Integer> res) {
if (res.size() == 1 << n) return true;
int last = res.get(res.size() - 1);
for (int i = 0; i < n; i++) {
int cur = 0;
// change 1 bit
int bitI = (last >> i) & 1;
if (bitI == 1) cur = last - (1 << i);
else cur = last + (1 << i);
if (!res.contains(cur)) {
res.add(cur);
if (DFS(n, res)) return true;
res.remove(res.size() - 1);
}
}
return false;
}
```