Gray Code

two methods are provided.

first one is from codeganker
这道题要求求出n位的格雷码对应的二进制数，主要在于找到一种格雷码的递增方法（gray code并不是唯一的，可以有多种）。
我们来看看有了n-1位的格雷码如何得到n位的格雷码呢？其实方法比较简单，首先在n-1位的格雷码前面都添加0作为前2^(n-1)个格雷码，它们一定是合法的因为除了第一位（都是0）其余位都跟n-1的格雷码一致，所以两两之间只相差一位，满足要求。接下来看看如何接上剩下的2^(n-1)个，我们把n-1位的格雷码倒序排列，然后在每个前面添加1，然后接到上述的前2^(n-1)个就可以了。首先因为是倒序过来，所以中间两个元素除去第一位其他都是一样的（因为原来最后一个，现在倒序过来就是第一个），而他们第一位分别是0和1，满足格雷码的要求。而剩下的元素因为我们是n-1位的格雷码倒序排列，所以两两都是满足要求的，加上前面都一样的位1，仍然满足条件。最后看看这些数字是不是都不一样，前半部分和后半部分肯定不会一样，而因为前半部分都是0开头，后半部分都是1打头，所以互相之间也不会有重复，可以看出覆盖了所有数字，而且依次下来均满足条件。
如此我们提出了格雷码的递推方法，我们只需要做一次位数的循环，每次根据上面结果构造当前位数的结果即可。算法复杂度是O(2+2^2+...+2^n-1)=O(2^n)，所以是指数量级的，因为是结果数量无法避免。空间复杂度则是结果的大小，也是O(2^n)。代码如下：

    vector<int> grayCode(int n) {
        vector<int> ret;
        if(n==0){
            ret.push_back(0);
            return ret;
        }
        ret.push_back(0);
        ret.push_back(1);
        for(int i=2;i<=n;i++){
            int tmp=1<<i-1;
            int vsize=ret.size();
            for(int j=vsize-1;j>=0;j--){
                ret.push_back(ret[j]+tmp);
            }
        }
        return ret;
    }

//second one. regard every gray code as a vertex of a graph, two vertex has an edge iff their gray code differ by one bit. Then do DFS from  the vertex of gray code 0

    vector<int> grayCode(int n) {
        int num=1<<n;
        int mark[num];
        for(int i=0;i<num;i++)
            mark[i]=0;
        vector<int> ret;
        dfs(n,0,mark,ret);
        return ret;
    }
    void dfs(int n, int v,int mark[],vector<int>& aqueue)
    {
         mark[v]=1;int tmp;
         aqueue.push_back(v);
         for(int i=0;i<n;i++)
         {
             tmp=v^(1<<i);
             if(mark[tmp]==0)
             {
                dfs(n,tmp,mark,aqueue);
                break;
             }
                
         }
    }