博文中会简要介绍Leetcode P0089题目分析及解题思路。

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

Example 1:

Input: 2
Output: [0,1,3,2]

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

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

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

深度优先搜索与回溯法

这里想讲解一下我个人关于这两种方法的思考。

回溯法是深度优先搜索的一个分支，在我以往的Leetcode题解博文里也经常会说“这是一道深度优先搜索的问题，这里是回溯法”，在我个人的观念里，回溯法是深度优先搜索的一个特例。

非回溯法的深度优先搜索虽然也是递归解法，也是在解决子问题，但是其探索的含义更浓一些，即每次先探索本层结点，然后根据情况探索合法的下层结点。而纯粹的递归问题，即回溯法问题，则专注于将问题分解为子问题，然后解决子问题。前者一般来说对本层还有探索的行为，并且可以随时中断搜索；而后者则是首先递归到最深处，解决最小子问题或者说元问题，然后根据递归结束条件再从最深处回溯到最上层，或者终止。

一个非回溯法的深度优先搜索问题，核心在于如何探索本层和如何进入下层；而一个纯递归（回溯法）问题，核心则在于如何利用下层结果解决上层问题，比方说上层需要得到一个排列，在解法上我们必须探索到最深处才能完整地生成这个排列，虽然我们无需向上层返回具体的值，但是实际上我们探索下层，恰恰是为了解决上层提出的“得到一个排列”这样的需求，所以也可以说上层依赖了下层的结果。

用大白话再打个比方，在一张地图上有一个target，旅者需要寻找到这个target。一个纯粹的搜索问题是要求旅者找到目标即可，旅者每走一步都会站在原地问“这里是不是目标了呢？”，如果是则终止搜索，如果不是则看看自己还能往哪走。而一个递归回溯问题则是要求旅者不仅要找到目标，还要知道如何从起点走到目标，这时旅者每走一步，站在原地都会问下一步“到目标的路径是什么样的呢？”，直到下一步说“我就是目标”，这时旅者走过的地方都会向上层汇报“这样走可以到目标”，最终在起点就可以形成一条到目标的通路。

总的来说，回溯法也是一种深度优先搜索。在解决问题的时候，想到使用深度优先搜索的时候，不仅要考虑能否分解问题，然后直接通过解决最小子问题（元问题）来解决上层对下层的依赖，即递归回溯；也要考虑是否可以使用非回溯法的深度优先搜索算法，每一层相对独立地存在，即纯粹的搜索。

题解

虽然说这道题是递归回溯问题，但是找到将问题分解成子问题的途径或者说策略也是一个难点。这里最好对格雷码有所了解。我们观察上述样例中的格雷码不难发现如下规律：

    n = 1,
    0 -> 1

    n = 2,
    00 -> 01 -> 11 -> 10

    n = 3,
    000 -> 001 -> 011 -> 010 -> 110 -> 111 -> 101 -> 100

    很容易发现，当n=k时，前2^(k-1)个格雷码和n=k-1时的格雷码序列一致，而后面2^(k-1)个格雷码则是前面的序列倒序以后，每个格雷码的第k-1位变为1（第0位是最低位）。  
    举个例子，观察n=3时，前4个和n=2时的序列一致，而第5个是110恰好是第4个格雷码010的第2位变为1。同理第6个是111恰好是第3个格雷码011的第2位变为1。
    这样一来我们就可以得到格雷码的生成方法，也即将问题分解城子问题的策略。

以下是Java的题解代码实现。

class Solution {
    public List<Integer> grayCode(int n) {
        int[] codes = new int[(int) Math.pow(2, n)];
        if (n == 0)
            return Arrays.asList(new Integer[] {0});
        
        this.encode(n, codes);
        return Arrays.stream(codes).boxed().collect(Collectors.toList());
    }
    
    private void encode(int n, int[] codes) {
        if (n == 1) {
            codes[0] = 0;
            codes[1] = 1;
        }
        else {
            this.encode(n-1, codes);
            int lastSize = (int) Math.pow(2, n-1);
            for (int idx=lastSize-1; idx>=0; --idx) {
                int next = codes[idx]|(1<<(n-1));
                
                codes[2*lastSize-1-idx] = next;
            }
        }
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> gray_codes(pow(2, n), 0);
        if (n == 0)
            return vector<int> {0};
        
        this->GenerateGrayCode(n, gray_codes);
        return gray_codes;
    }
    
private:
    void GenerateGrayCode(const int n, vector<int> &gray_codes) {
        if (n == 1) {
            gray_codes[0] = 0;
            gray_codes[1] = 1;
            return;
        }
        else {
            this->GenerateGrayCode(n-1, gray_codes);
            int last_size = pow(2, n-1);
            for (int idx=last_size-1; idx>=0; --idx) {
                int next = (gray_codes[idx]|(1L<<(n-1)));
                gray_codes[2*last_size-idx-1] = next;
            }
            return;
        }
    }
    
};