LeetCode89 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.

本题重点是理解格雷码的生成规律，先试着写出3位格雷码：
000 - 0
001 - 1
011 - 3
010 - 2
110 - 6
111 - 7
101 - 5
100 - 4
或
000 - 0
001 - 1
011 - 3
010 - 2
110 - 6
100 - 4
101 - 5
111 - 7

一开始我很纠结到底是哪种。。。网上查阅+自己对于2位的情况后，确定应该使用第一种！！！

然后看0132与6754
发现诶？！！！
6754-4444=2310

0132与2310正好是逆序！！！

有没有很神奇？！！

ok

了解这点以后，可以采用回溯，对于n位greycode：
1 先dfs(n-1)获取n-1位greycode
2 将n-1位的greycode都加入n位的list中
3 将n-1位的值都加上2^(n-1)次方的offset后，再加入list中

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> codes = new ArrayList<>();
        dfs(n, codes);
        return codes;
    }
    
    public void dfs(int n, List<Integer> codes) {
        if (n == 0) {   
            codes.add(0);
            return;
        }
        
        dfs(n-1, codes);
        int offset = (int)Math.pow(2,n-1);
        int size = codes.size()-1;
        for (int i = size; i >= 0; i--) {
            codes.add(offset + codes.get(i));
        }
    }
    
}