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 - 001 - 111 - 310 - 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.

思路：

参考自：

My idea is to generate the sequence iteratively. For example, when n=3, we can get the result based on n=2.

00,01,11,10 -> (000,001,011,010 ) (110,111,101,100). The middle two numbers only differ at their highest bit, while the rest numbers of part two are exactly symmetric of part one. It is easy to see its correctness.

Code is simple:

vector
     
       grayCode(int n)     {         vector
      
       ret;         ret.push_back(0);         for (int i = 0; i < n;i++)         {             int size = ret.size();             for (int j = size-1; j >=0;j--)             {                ret.push_back(ret[j] | 1 << i);             }         }         return ret;     }