[LeetCode] Gray Code

Problem Statement (link):

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.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

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

Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Analysis:
The OJ could only judge one instance of gray code sequence, based on wiki page, the sequence of gray code when n=3 is:

000
001
011
010
110
111
101
100

If we observe carefully, we found out that except for the MSB, where the first four numbers are all 0's and last four numbers are all 1's, the bit sequence are mirrored as color coded above. Thus, our algorithm will build new gray codes when n=k, based on the gray codes when n=k-1. This is an iterative process.

The time complexity is exponential - O(2^n), as we need 1+2+4+...+(2^(n-1)) operations.

Code:

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

        for (int k=0; k<n; k++) {
            int sz=res.size(); //res's size is changing, need to assign a fixed value
            for (int i=sz-1; i>=0; i--) {
                res.push_back((1<<k)+res[i]);
            }
        }
        return res;
    }
};