[数据结构与算法]生成所有的格雷码

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。
n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
每个整数都在范围 $[0,2^n?1]$ 内（含 0 和 $2^n?1$）
第一个整数是 0
一个整数在序列中出现 不超过一次
每对 相邻 整数的二进制表示 恰好一位不同 ，且
第一个 和 最后一个 整数的二进制表示 恰好一位不同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gray-code
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
0 1 3 2 是一组标准的格雷码
因为[0,1,3,2] 的二进制表示是 [00,01,11,10] 。

• 00 和 01 有一位不同
• 01 和 11 有一位不同
• 11 和 10 有一位不同
• 10 和 00 有一位不同

在解决生成格雷码的问题时，力扣上的要求是得到一个结果即可，但是我计算出所有可能的组合，这样做最后的结果如下图所示，超时了。

但是，我认为，如果在求所有的格雷码组合时，可以考虑使用我的方法，其思想是回溯。

代码生成的是以0为起点，生成格雷码的组合。

import org.junit.Test;

import java.util.LinkedList;
import java.util.List;

public class w0405_grayCode {
    public List<List<Integer>> track = new LinkedList<>();
    public List<Integer> list = new LinkedList<>();
    public boolean visited[];

    public List<Integer> grayCode(int n) {
        visited = new boolean[(int) (Math.pow(2, n))];
        list.add(0);
        visited[0] = true;
        gray(1, n);
        for (int i = 0; i < track.size(); i++) {
            System.out.println(track.get(i).toString());
        }
        return track.get(0);
    }

    @Test
    public void test() {
        grayCode(3);
    }

    public void gray(int start, int n) {
        if (start == (int)Math.pow(2, n)) {
            track.add(new LinkedList<>(list));
            return;
        }
        for (int i = 1; i < Math.pow(2, n); i++) {
            if (visited[i])
                continue;
            if (isTrue(i, start, (int)Math.pow(2, n))) {
                visited[i] = true;
                list.add(i);
                gray(start + 1, n);
                visited[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }

    public boolean isTrue(int num, int start, int n) {
        if (start != n - 1) {
            boolean flag = true;
            int last = list.get(list.size() - 1);
            int res = num ^ last;
            return (res & (res - 1)) == 0;
        }
        int last = list.get(list.size() - 1);
        int res1 = num ^ last;
        int res2 = num ^ 0;
        return (res1 & (res1 - 1)) == 0 && (res2 & (res2 - 1)) == 0;
    }
}

运行结果如下：

解释一下我的代码，isTrue 函数的作用是检查选择 i 是否满足格雷码的条件，那么该如何判断呢？如果选择 i ，和 list 中 最后一位相比较，判断其二进制是否相差一个1，我的思路是：把这两个数进行异或处理，如果只相差一个数，那么异或得出的结果是2的整数次方，问题又来了，怎样判断一个数是 2 的整数次方呢 ？
如果一个数是2的整数次方时，可以表示为10…0，把这个数减一，得到的数为01…1，再把两个数进行与操作，判断最终的结果是否为0，如果为0，则表示此数为2的整数次方。
除此之外，当遍历到最后一位时，不仅需要把这个结果和前一位进行比较，还要与0进行比较。