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.

这道题似乎不是一个backtracking的题，不过也可以用backtracking的方法来做，gray code是有一定规律的，backtracking没有必要

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>(n * n);
        if(n == 0) {
            res.add(0);
            return res;
        }

        res = grayCode(n - 1);
        List<Integer> lastHalf = new ArrayList<>((n - 1) * (n - 1));
        for(int i = res.size() - 1; i >= 0; i--) {
            lastHalf.add((1 << (n - 1)) + res.get(i));
        }
        res.addAll(lastHalf);

        return res;
    }
}