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;
        }
    }
};