## Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer

nrepresenting 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 - 0 01 - 1 11 - 3 10 - 2

Note:

For a givenn, 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.

//代码不长，思路挺intuitive的。 //递归，先写出base condition。n == 1 and n == 0 //对于n = k, 先求出n = k - 1的情况，然后将结果拷贝到re中，因为n = k 的前一半结果相当于在gray code的最前方添一个0，并没有改变结果。 //对于后一半结果，需要逆序遍历前一半结果并加一个plus，plus的值等于2^(n-1)。 //复杂度为o(n^2) class Solution { public: vector<int> grayCode(int n) { vector<int> re; if(n == 0){ re.push_back(0); return re; } if(n == 1){ re.push_back(0); re.push_back(1); return re; } else{ re = grayCode(n - 1); size_t len = re.size(); int plus = pow(2, n - 1); for(int i = len - 1; i >=0; i--){ re.push_back(re[i] + plus); } return re; } } };