[Leetcode] 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.

We could obtain the n+1th solution from what we have from nth solution. Since nth solution has already satisfy the property of gray code.

1. We get a copy of the nth solution.
2. We reverse the copy, now the copy still satisfy the gray code.
3. For each reversed element, we add 2^n to it, thus there will be a leading 1 compared to the original list.
4. Append this list to the original, and we have obtain the n+1th solution.

After the reversion, the first element of the copy list would be the same with the last of the original element. In order to satisfy the gray code property, we add a leading 1 to all of the elements in the copy list. This would not break the gray code property in the copy list, and would make sure the first element in the copy list differ one bits from the last one in the original list. Thus the gray code property is maintained.

    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<Integer>();
        res.add(0); // base case
        for(int i = 0; i < n; i++) {
            int base = (1 << i);
            int m = res.size();
            for(int j = m-1; j >= 0; j--) {
                res.add(res.get(j) + base);
            }
        }
        return res;
    }