Description

The description of this problem is very vague. It is even unclear what is the gray code with 3 bits. What is worse, according to wikipedia, there do exist various ways of defining gray code.

With some “guessing” work, the gray code used in this problem for 3 bits is like this

0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0

Then it is easy to see that the eight numbers are symmetric without the first bit. Thus we can construct n-bit gray codes via a recursive procedure. One thing worth noting is that when n = 0, codeVec is not empty.

Though it seems very natural to code the solution in a recursive way, it is actaully easier (and of course more efficient) to implement it in iterative manner.

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> codeVec;
        codeVec.push_back(0);
        int unit = 1;
        for (int i = 0; i < n; ++ i){
        	for (int j = codeVec.size()-1; j >=0; -- j)
        		codeVec.push_back(codeVec[j] + unit);        		        	
        	unit *= 2;
        }
        return codeVec;
    }
};