Just observe:

```
n=1
0
1
n=2
00
01
--- now comes 2nd with 1
11 (=10 + 01)
10 (=10 + 00)
n=3
000
001
---- now comes 2nd with 1
011 (=010 + 001)
010 (=010 + 000)
---- now comes 3rd with 1
110 (=100 + 010)
111 (=100 + 011)
101 (=100 + 001)
100 (=100 + 000)
```

So it seems the gray code is formed by "prefix + the reverse of previous sequence"

Now the Java code can solve this easily:

```
public List<Integer> grayCode(int n) {
List<Integer> res = new ArrayList<>();
res.add(0);
if(n==0)
return res;
if(n==1) {
res.add(1);
return res;
}
int prefix = 1<<(n-1);
res = grayCode(n-1);
for(int i=res.size()-1; i>=0; i--)
res.add(prefix+res.get(i));
return res;
}
```