题解 | #生成格雷码# 递归

参考大佬的java做法，

由题意知，每递归一层，整体vector长度乘以2倍，由于相邻的编码只能有一个数不同，因此需要事先计算出添加1的位置

#include <vector>
class GrayCode {
  public:
    vector<string> getGray(int n) {
        if (n == 1) {
            return {"0", "1"};
        }
        vector<string> prefix = getGray(n - 1);
        int size = prefix.size();
        vector<string> result(size * 2);
        for (int i = 0; i < size; i++) {
            result[i] = "0" + prefix[i];
            result[size + i] = "1" + prefix[size - i - 1];
        }
        return result;
    }
};

时间复杂度：O(2^n),其中n是输入的整数

空间复杂度：O(n+2^n),递归调用的栈空间复杂度为O(n),而字符串大小为O(2^n)