89. Gray Code

An n-bit gray code sequence is a sequence of 2n integers where:

• Every integer is in the inclusive range [0, 2n - 1],
• The first integer is 0,
• An integer appears no more than once in the sequence,
• The binary representation of every pair of adjacent integers differs by exactly one bit, and
• The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any valid n-bit gray code sequence.

• back tracking solution
• Time : O(2^n * logn)
• Space : O(n)

c++

class Solution {
    bool helper(vector<int>& res, int& n, unordered_set<int>& us) {
        if(res.size() == 1<<n) return true;
        else {
            int last = res.back();
            for(int i = 0; i < n; i++) {
                bool bit = (last & (1<<i));
                int next = last + (bit ? -(1<<i) : (1<<i));
                if(us.count(next)) continue;
                res.push_back(next);
                us.insert(next);
                if(helper(res, n, us)) return true;
                res.pop_back();
                us.erase(next);
            }
        }
        return false;
    }
public:
    vector<int> grayCode(int n) {
        int mask = (1<<n) - 1;
        unordered_set<int> us{0};
        vector<int> res{0};
        helper(res, n, us);
        return res;
    }
};

• greedy solution with tricky idea

c++

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res{0};
        for(int i = 0; i < n; i++) {
            int sz = res.size();
            for(int j = sz - 1; j >= 0; j--) {
                res.push_back(res[j] | 1<<i);
            }
        }
        return res;
    }
};