(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

Thoughts:
The tricky part of this question is to recognize the recursive structure here. For n = 0, sol = [0], that’s the base case. For recursive step, let’s take n = 2 and n = 3 as examples. n = 2, sol = [0, 1, 3, 2]; n = 3, sol = [0, 1, 3, 2, 6, 7, 5, 4]. Look at these two solutions, we see when n = 3, we add 4 more elements [6, 7, 5, 4] and they are just [2+4, 3+4, 1+4, 0+4]. That is sol(n+1) = sol(n) + [ reverse(sol(n)) + 2^(n) ].

Code (Java):

import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> grayCode(int n) {
ArrayList<Integer> sol = new ArrayList<Integer>();
if(n == 0) {
return sol;
} else {
ArrayList<Integer> previous = grayCode(n - 1);
for(int i = previous.size() - 1; i >= 0; --i) {
sol.add((int)Math.pow(2.0, n - 1) + previous.get(i));
}
return sol;
}
}
}

Code (C++):

class Solution {
public:
vector<int> grayCode(int n) {
if(n == 0) {
vector<int> sol;
sol.push_back(0);
return sol;
} else {
vector<int> previous = grayCode(n - 1);
vector<int> sol(previous);
for(int i = previous.size() - 1; i >= 0; --i) {
sol.push_back((int)pow(2.0, n - 1) + previous[i]);
}
return sol;
}
}
};