Leetcode鏈接 : https://leetcode-cn.com/problems/gray-code/

問題描述：

格雷編碼是一個二進制數字系統，在該系統中，兩個連續的數值僅有一個位數的差異。給定一個代表編碼總位數的非負整數 n，打印其格雷編碼序列。格雷編碼序列必須以 0 開頭。

格雷碼特點：

• 位數為n時,格雷碼的個數為 2^n(n>1) ，且要求格雷碼從零開始。
• 格雷碼在組成時遵循鏡像關係。在構成n位格雷碼時，需要已知n-1位格雷碼的序列，且當n>0時，n位格雷碼的長度為n-1格雷碼的兩倍。對鏡像關係解釋如下圖所示，當n=2時，格雷碼個數為4，從中間分開，格雷碼後n-1位關於中心對稱。

解題思路

由上可知，解決格雷碼問題的兩個關鍵點：（1）邊界條件：n=0時，res=[] . （2）從n-1位格雷碼到n位格雷碼的遞推函數：原有n-1位格雷碼不變，然後對原n-1位格雷碼逆序遍歷，並對每個數執行g[i]+=( 1<<(n-1) ),append到原n-1位格雷碼後。
故此問題有兩種解法

1. 自頂而下（回溯），從n位格雷碼求解開始，進行遞歸，直到碰到n=0邊界條件返回。
2. 自底而上（遞推），從n=0，開始逐步都求解n=1,n=2...n=n,直到得到n位格雷碼。

下面給基於遞歸的C++實現

class Solution {
public:
    vector<int> grayCode(int n) {
        if(n==0){
            vector<int> vec;
            vec.push_back(0);
            return vec;
        }
        vector<int> pre=grayCode(n-1);
        int add_item=1<<(n-1);
        int size=pre.size();
        for(int i=size-1;i>=0;i--){
            pre.push_back(add_item+pre[i]);
        }
        return pre;
    }
    
};