The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integernrepresenting the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, givenn= 2, return[0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a givenn, 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.

Solution 1: 镜面排列，n位元的格雷码可以从n-1位元的格雷码以上下镜射后加上新位元的方式快速的得到，如下图所示一般。

根据这条性质，求n位的gray code，可以根据n－1位的gray code来求。只要将n－1位的gray code的答案在前面加一位0以及n－1位的gray code的答案reverse之后全部在前面加一位1即可。

    public List<Integer> grayCode(int n) {
        List<Integer> ans = new ArrayList<Integer>();
        if(n < 2){
            for(int i = 0; i <= n; i++){
                ans.add(i);
            }
            return ans;
        }
        ans = grayCode(n - 1);
        List<Integer> res = reverse(ans);
        int num = 1 << (n - 1);
        for(int i = 0; i < res.size(); i++){
            ans.add(res.get(i) | num);
        }
        return ans;        
    }
    private List<Integer> reverse(List<Integer> ans){
        List<Integer> temp = new ArrayList<Integer>();
        for(int i = ans.size() - 1; i >= 0; i--){
            temp.add(ans.get(i));
        }
        return temp;
    }

Solution 2: 用set来保存已经产生的结果，我们从0开始，遍历其二进制每一位，对其取反，然后看其是否在set中出现过，如果没有，我们将其加入set和结果res中，然后再对这个数的每一位进行遍历，以此类推就可以找出所有的格雷码了。

    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(n <= 1){
            for(int i = 0; i <= n; i++){
                res.add(i);
            }
            return res;
        }
        HashSet<Integer> set = new HashSet<Integer>();
        helper(n, set, 0, res);
        return res;
    }

    private void helper(int n, HashSet<Integer> set, int curt, ArrayList<Integer> res){
        if(!set.contains(curt)){
            set.add(curt);
            res.add(curt);
        }
        for(int i = 0; i < n; i++){
            int temp = curt;
            //如果当前位为0，则变为1
            if((temp & (1 << i)) == 0){
                temp |= 1 << i;
            }else{
            //如果当前位为1，则变为0，因为是&操作，为了保证其他位不变，必须使其他位为1
                temp &= ~(1 << i);
            }
            if(set.contains(temp)){
                continue;
            }
            helper(n, set, temp, res);
        }
    }