C++_O(2^n)_Accepted_with brief explanation

• For me, I did not have any background in CS or EE, so I just use method mentioned in https://discuss.leetcode.com/topic/1011/what-is-the-best-solution-for-gray-code-problem-no-extra-space-used-and-no-recursion/2 Thanks a lot!

• The logic should be like this. Each time we could only change 1 digit in our previous number. In order for clear explanation, I will n = 3. First, let's add 000 in to our res, now we have 1 number. Next step is adding digit 1 to 000. We add 1 from the last number of our res and last digit of that number. so we put 001 in to res.

• Now we have res = [000, 001]. The next step is add 1 in to the second digit of each number, but we should notice that if we first add 1 to 000 and get 010 and push it back to res, we will find that 001 and 010 have 2 different digits. So we first add 1 to 001 and then add 1 to 000, we now get res = [000, 001, 011, 010]. This step secures our result is correct, because for the 011, it is derived from 001 , so there will be only 1 different digit, for 010, after 000 add 1 to its second digit, the first and second digits are the same as the one derived from 001, so the new one will also be 1 digit different from previous one in res vector.

• Then add 1 to the first digit and use above algorithm. res = [000,001,011,010,110,111,101,100].
``````class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res(1,0);
for(int i = 0; i < n; i++){
int k = res.size();
while(k > 0){
k--;
int tmp = res[k] + (1 << i);
res.push_back(tmp);
}
}
return res;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.