```
vector<int> grayCode(int n) {
vector<int> gc;
gc.reserve(pow(2, n));
for (int bit = 0, mask = 1; bit <= n; bit++) {
if (bit == 0) gc.push_back(0); // First element is always 0 (given)
else {
// Gray code with the new bit can be easily generated by iterating BACKWARDS
// the gray code we have generated so far and adding a '1' in the MSB.
//
// This works because the very first number with the new bit obviously
// differs with its previous in the MSB (1). From then on, although the MSB
// stays 1 the remaining bits are previously generated gray code, so they
// must differ only by 1 bit.
//
// Example: n = 4
// bit gray_code
// 0 0
// 1 1{gray_code(0) iterating backwards}
// {0, 1}
// 2 1{gray_code(1) iterating backwards}
// {0, 1, 11, 10}
// 3 1{gray_code(2) iterating backwards}
// {0, 1, 11, 10, 110, 111, 101, 100}
//
for (int j = pow(2, bit - 1) - 1; j >= 0; j--) {
gc.push_back(mask | gc[j]);
}
mask <<= 1;
}
}
return gc;
}
```