# [leetcode] Gray Code

### Gray Code

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

```//代码不长，思路挺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;
}
}
};``` This site uses Akismet to reduce spam. Learn how your comment data is processed.