gray code is also knows as reflected binary code

when n is 1:

gray binary - decimal it represents

0 - 0

1 - 1

when n is 2, the first half from n = 1keeps in the order, the second half reverse and then add 2 * (n - 1) to each element

gray binary(n - 1) - gray code(n) - decimal it represents

0 - 00 - 0

1 - 01 - 1

1 - 11(1 + 2) - 2

0 - 10(0 + 2) - 3

it will be the same from i - 1 to i (1 <= i <= n)

so we can use this feature to solve this problem

For each i, it will run 2*(i -1) operations

The total operations will be 2 + 2^2 + 2^3 + 2^4 + ... + 2^(n -1) = 2^n - 2

Therefore the time complexity is O(2^n)

```
public class Solution {
public List<Integer> grayCode(int n) {
List<Integer> grayCodeDecimal = new ArrayList<>();
if (n < 0) {
return grayCodeDecimal;
}
if (n == 0) {
grayCodeDecimal.add(0);
return grayCodeDecimal;
}
for (int i = 1; i <= n; ++i) {
if (i == 1) {
grayCodeDecimal.add(0);
grayCodeDecimal.add(1);
} else {
int base = (int) Math.pow(2, i - 1);
for (int j = base - 1; j >= 0; --j) {
grayCodeDecimal.add(base + grayCodeDecimal.get(j));
}
}
}
return grayCodeDecimal;
}
}
```