# 89 - Gray Code

解法一 - 失敗的無窮 Backtracking

最一開始的直覺是：

1. 用一個 dict 來存所有要被放進 res 的數(範圍從 $0$ 到 $2^n-1$)

2. 用 recursive function 來一次翻轉一個 bit，確認只要翻轉完 bit 的 int 有在 dict 裡面，就加到答案裡

實作如下：

class Solution {
public:
    vector<int> grayCode(int n) {
        // Prepare dict for check
        int total_num = pow(2, n);
        unordered_set<int> dict;
        for(int i=0; i<total_num; i++)
            dict.insert(i);

        vector<int> res;
        int tmp = 0;

        helper(n, dict, res, tmp,  0, 'I');

        return res;
    }

private:
    void helper(int total_bits, unordered_set<int>& dict, vector<int>& res, int& tmp, int bit, char dir) {
        if(dict.find(tmp)!=dict.end()){
            dict.erase(dict.find(tmp));
            res.push_back(tmp);
        }

        if(dict.empty())
            return;

        // Touch the end, change direction
        if(bit == total_bits-1 && dir == 'I') dir = 'D';
        if((bit == 0) && (dir == 'D')) dir = 'I'; 

        tmp ^= 1UL << bit;
        if(dir == 'I')
            helper(total_bits, dict, res, tmp, bit+1, dir);
        else
            helper(total_bits, dict, res, tmp, bit-1, dir);
        tmp ^= 1UL << bit;
    }
};

基本上這個解法在 n 比 3 還小的時候都對，可惜到 n==4 時，就無法找到 5 跟 12 這兩個 case 而會陷入無窮 recursion（全面啟動?ＸＤ）。

解法二 - 動態規劃

這一篇已經將答案整理得非常清楚了！這解法滿聰明的，可以好好學習一下。

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int>res(1,0);

        for(int i=0;i<n;i++){
            int size=res.size();
            for(int j=size-1;j>=0;j--){
                res.push_back(res[j]|1<<i);
            }
        }

        return res;
    }
};